Ok để có độ sâu ngăn xếp tuyến tính tỷ lệ thuận với một số kích thước đầu vào?

Question

Khi lập trình bằng Java (hoặc bất kỳ ngôn ngữ thủ tục nào khác cho vấn đề đó), tôi thường chọn giữa giải quyết một cách đệ quy và giải quyết nó lặp đi lặp lại. Tùy chọn đệ quy thường thanh lịch hơn so với giải pháp lặp nên tôi thường tìm giải pháp đệ quy. Với một ngoại lệ:

Lo lắng về tràn ngăn xếp Tôi có xu hướng tránh các giải pháp đệ quy nếu độ sâu ngăn xếp tối đa tỷ lệ thuận với kích thước đầu vào (hoặc tệ hơn). Tuy nhiên, tôi nhận ra rằng trong nhiều ngôn ngữ khác (ngay cả những ngôn ngữ nhắm vào JVM như Scala và Clojure) nhiều thuật toán, chẳng hạn như các thuật toán danh sách cơ bản, thường được biểu diễn một cách đệ quy nơi độ sâu stack tối đa tỉ lệ với độ dài của danh sách. ⁽¹⁾ Vì vậy, là những lo lắng của tôi về việc tràn ngăn xếp trong các thuật toán xếp chồng-chiều sâu-tuyến tính hợp lý?

TL; DR: "Độ phức tạp chiều sâu ngăn xếp" được coi là hợp lý? Logarit phức tạp, tìm kiếm nhị phân đệ quy Ví dụ, O (log N) chắc chắn là ok, nhưng làm thế nào về O (N), O (N log N), O (N)? Bạn thường vẽ đường ở đâu? ⁽²⁾

^{(1) Tôi nhận ra rằng ngôn ngữ như vậy đôi khi hỗ trợ những thứ như @tailrec, nhưng câu hỏi này liên quan đến Java, C#, vv
(2) Lưu ý rằng tôi không quan tâm đến CPU overhead vv Chỉ cần chiều sâu ngăn xếp.}

Answer 1

Bạn không thể trả lời câu hỏi này mà không tự hỏi mình nhập kích thước nào bạn muốn có thể hỗ trợ.

Độ phức tạp của không gian tuyến tính trên ngăn xếp hoàn toàn ổn nếu bạn đang xử lý một cỗ bài chơi và có thể hoàn toàn vô vọng nếu bạn đang dùng các tệp văn bản lớn. Bạn cần phải tìm ra kích thước đầu vào tối đa cho ứng dụng của bạn, hay đúng hơn, đầu vào lớn nhất mà bạn không quan tâm đến nó không thành công.

Chúng tôi làm việc này mọi lúc. Ví dụ, mỗi khi bạn khai báo một mảng trong Java, bạn biết rằng mảng không thể có nhiều hơn 2 các phần tử trong đó. Điều đó có quan trọng không? Điều đó có nghĩa là chương trình bị hỏng? Chắc là không; nhưng đôi khi nó có, nếu đầu vào lớn là một cái gì đó bạn muốn để có thể đối phó với.

Vì vậy, tôi không nghĩ bạn có thể quá chi tiết về điều này.Bạn sẽ nói gì nếu có ai đó hỏi (theo các thuật ngữ khá chung chung) thời gian phức tạp là gì? Bạn có thể nói một số nguyên tắc chung: thường là tuyến tính là OK, thường là mũ là xấu ... nhưng câu trả lời thực sự là, nó phụ thuộc vào những gì bạn đang làm.

Answer 2

Độ phức tạp của độ sâu ngăn xếp là một điều cần cân nhắc, nhưng một thứ khác là chính kích thước đầu vào.

Nếu vấn đề loại trừ đầu vào lớn của miền (đối với mở rộng thời gian trong quá trình phát triển), thì chúng ta có thể đi giải pháp đệ quy (tất nhiên, giải pháp đệ quy không được vượt quá dung lượng của ngăn xếp với đầu vào lớn nhất có thể).

Nếu kích thước đầu vào không được xác định, O (1) chiều sâu ngăn xếp hoặc độ sâu ngăn xếp O (log N) là chấp nhận được, IMHO. Có thể là O (log N) có thể không được chấp nhận nếu giới hạn trên thực tế trên kích thước đầu vào là lớn về mặt thiên văn mà nó vượt quá khả năng ngăn xếp. Tuy nhiên, tôi nghĩ trường hợp như vậy sẽ khá hiếm.