Đệ quy và Big O

Question

Tôi đã làm việc thông qua một bài tập về nhà Khoa học Máy tính gần đây liên quan đến đệ quy và ký hiệu big-O. Tôi tin rằng tôi hiểu điều này khá tốt (chắc chắn không hoàn toàn, mặc dù!) Nhưng có một câu hỏi đặc biệt đó là đem lại cho tôi những vấn đề nhất. Điều kỳ lạ là bằng cách nhìn nó, nó có vẻ là một trong những đơn giản nhất trên bài tập về nhà.

Cung cấp tốc độ tăng trưởng tốt nhất sử dụng ký hiệu lớn-Oh cho giải pháp cho sự tái diễn sau đây?

T (1) = 2

T (n) = 2T (n - 1) + 1 với n> 1

Và các lựa chọn là:

• O (n log n)
• O (n^2)
• O (2^n)
• O (n^n)

Tôi hiểu rằng O lớn hoạt động như một giới hạn trên, để mô tả số lượng tính toán nhiều nhất, hoặc thời gian chạy cao nhất, chương trình hoặc quá trình đó sẽ mất. Tôi cảm thấy như đệ quy đặc biệt này nên là O (n), vì, nhiều nhất, đệ quy chỉ xảy ra một lần cho mỗi giá trị n. Vì n không có sẵn, nó tốt hơn thế, O (nlogn), hoặc tệ hơn, là ba tùy chọn khác.

Vì vậy, câu hỏi của tôi là: Tại sao không phải là O (n) này?

Answer 1

Có một số cách khác nhau để giải quyết sự tái diễn: thay thế, tái phát cây và định lý tổng thể. Định lý chính sẽ không hoạt động trong trường hợp, bởi vì nó không phù hợp với dạng định lý tổng thể.

Bạn có thể sử dụng hai phương pháp khác, nhưng cách dễ nhất cho vấn đề này là giải quyết nó lặp đi lặp lại.

T (n) = 2T (n-1) + 1
T (n) = 4T (n-2) + 2 + 1
T (n) = 8T (n-3) + 4 + 2 + 1
T (n) = ...

Xem mẫu?

T (n) = 2 ^n-1 ⋅T (1) + 2 ^n-2 + 2 ^n-3 + ... + 1
T (n) = 2 ^{n -1} ⋅2 + 2 ^n-2 + 2 ^n-3 + ... + 1
T (n) = 2 ⁿ + 2 ^n-2 + 2 ^n-3 + ... + 1

Vì vậy, giới hạn chặt chẽ nhất là Θ (2 ⁿ).

Answer 2

Tôi nghĩ điều này sẽ theo cấp số nhân. Mỗi gia số cho n làm cho giá trị lớn gấp đôi.

T(2) = 2 * T(1) = 4 
T(3) = 2 * T(2) = 2 * 4 
... 

T (x) sẽ là thời gian chạy của chương trình sau đây (ví dụ):

def fn(x): 
if (x == 1): 
    return # a constant time 
# do the calculation for n - 1 twice 
fn(x - 1) 
fn(x - 1) 

Answer 3

Tôi nghĩ rằng bạn đã hiểu lầm câu hỏi một chút. Nó không hỏi bạn phải mất bao lâu để giải quyết sự tái diễn. Đó là yêu cầu những gì lớn-O (các asymptotic ràng buộc) của chính nó là giải pháp.

Điều bạn phải làm là đưa ra giải pháp biểu mẫu đã đóng, i. e. công thức không đệ quy cho T (n), và sau đó xác định những gì lớn-O của biểu thức đó.

Answer 4

Tôi nghĩ điều này sẽ theo cấp số nhân. Mỗi lần tăng đến n mang lại gấp đôi tính toán.

Không, không. Hoàn toàn ngược lại:

Hãy xem xét rằng đối với n lần lặp lại, chúng tôi nhận được thời gian chạy R. Sau đó cho n + 1 lặp lại chúng tôi sẽ nhận được chính xác R + 1.

Như vậy, tốc độ tăng trưởng là hằng số và thời gian chạy tổng thể thực sự O (n) là.

Tuy nhiên, tôi nghĩ rằng giả định Dima về câu hỏi là đúng mặc dù giải pháp của ông là quá phức tạp:

Những gì bạn phải làm là để tìm ra một giải pháp hình thức đóng cửa, i. e. công thức không đệ quy cho T (n), và sau đó xác định những gì lớn-O của biểu thức đó.

Đó là đủ để kiểm tra kích thước tương đối của T (n) và T (n + 1) lặp đi lặp lại và xác định tốc độ tăng trưởng tương đối. Số tiền rõ ràng gấp đôi trực tiếp cho sự tăng trưởng tiệm cận.

Answer 5

Câu hỏi đặt ra là yêu cầu ký hiệu lớn-Oh cho giải pháp cho sự tái diễn, chứ không phải chi phí tính toán sự tái diễn.

Nói cách khác: sự tái sản xuất:

1 -> 2 
    2 -> 5 
    3 -> 11 
    4 -> 23 
    5 -> 47 

gì lớn-Oh ký hiệu mô tả tốt nhất dãy 2, 5, 11, 23, 47, ...

Cách đúng để giải quyết đó là giải các phương trình lặp lại.

Answer 6

Trước hết, tất cả bốn câu trả lời đều tệ hơn O (n) ... O (n * log n) phức tạp hơn O (n) cũ. Những gì lớn hơn: 8 hoặc 8 * 3, 16 hoặc 16 * 4, v.v.

Đến câu hỏi thực tế. Các giải pháp chung rõ ràng có thể được giải quyết trong thời gian liên tục nếu bạn không làm đệ quy

(T (n) = 2^(n - 1) + 2^(n) - 1), do đó, đó không phải là những gì họ ' hỏi lại.

Và như bạn có thể thấy, nếu chúng ta viết mã đệ quy:

int T(int N) 
{ 
    if (N == 1) return 2; 
    return(2*T(N-1) + 1); 
} 

Đó rõ ràng là O (n).

Vì vậy, có vẻ như đó là một câu hỏi bị đặt sai, và có thể họ đang yêu cầu bạn tăng trưởng của hàm, chứ không phải sự phức tạp của mã. Đó là 2^n. Bây giờ hãy làm phần còn lại của bài tập ở nhà của bạn ... và nghiên cứu về O (n * log n)

Answer 7

Việc tính toán một giải pháp dạng khép kín cho đệ quy thật dễ dàng. Bằng cách kiểm tra, bạn đoán rằng giải pháp là

T(n) = 3*2^(n-1) - 1

Sau đó, bạn chứng minh bằng cảm ứng rằng đây thực sự là giải pháp. trường hợp cơ sở:

T(1) = 3*2^0 - 1 = 3 - 1 = 2. OK.

cảm ứng:

Suppose T(n) = 3*2^(n-1) - 1. Then 
T(n+1) = 2*T(n) + 1 = 3*2^n - 2 + 1 = 3*2^((n+1)-1) - 1. OK. 

nơi bình đẳng đầu tiên xuất phát từ định nghĩa tái phát, và lần thứ hai từ giả thuyết quy nạp. QED.

3 * 2^(n-1) - 1 rõ ràng là Theta (2^n), do đó câu trả lời đúng là câu trả lời thứ ba.

Đối với những người trả lời O (n): Tôi không thể đồng ý nhiều hơn với Dima. Vấn đề là không phải yêu cầu giới hạn trên chặt chẽ với độ phức tạp tính toán của thuật toán để tính T (n) (bây giờ là O (1), vì dạng đóng của nó đã được cung cấp). Vấn đề yêu cầu các ràng buộc trên chặt chẽ ràng buộc trên T (n) chính nó, và đó là một số mũ.