Tính toán ký hiệu O lớn với đệ quy

Question

Tôi đã cố gắng hiểu thời gian chạy trường hợp xấu nhất của Chữ ký Big O. Nhưng tôi vẫn không hiểu lắm.

Đây là một số mã mà tôi đã viết gần đây:

def g(n): 
    if n==0: 
     return 1 
    elif n==1: 
     return 2 
    else: 
     n_div=n//2 
     n_mod=n%2 
     return g(n_div)*g(n_mod) 

Vì vậy, tôi hy vọng rằng tôi ít nhất là ngay rằng:

def g(n): 
    if n==0: 
     return 1 

và:

elif n==1: 
    return 2 

là O (1), rất ổn định.

Nhưng còn phần else.

Có phải O (n) vì nó phụ thuộc vào số n mà tôi chọn không?

Bất cứ ai có thể giải thích về độ phức tạp Big O của phần else là gì?

Answer 1

Bạn đã nhận thấy rằng bạn có thể tách chức năng của mình thành 3 trường hợp riêng lẻ và đã xác định rằng 2 trường hợp đầu tiên là O (1). Thứ ba hơi phức tạp hơn một chút nhưng bạn có thể tách nó thành hai phần.

Các đệ quy rõ ràng xảy ra từ:

g(n//2)*g(n%2) 

Chúng tôi có thể thấy ngay rằng n%2 sẽ đánh giá hoặc 0 hoặc 1, mà sẽ giải quyết một trong 2 trường hợp đầu tiên một lần nữa, vì vậy chúng tôi có thể bỏ qua đó. Để lại chúng tôi với g(n//2). Bằng cách viết lại này như một vòng lặp in ấn và kiểm tra đầu ra bạn sẽ nhận thấy một cái gì đó:

>>> n = 37 
>>> while n > 1: 
...  n //= 2 
...  print(n) 
... 
18 
9 
4 
2 
1 

Như bạn có thể thấy các điều khoản giảm một nửa mỗi lần, và tương tự xảy ra trong đệ quy. Đây là lôgarít.

Kết quả là trường hợp xấu nhất cho hàm này là O (logn).

Bạn có thể tìm hiểu thêm về ý nghĩa thực sự của nhật ký trong ký hiệu Big-O bằng cách xem this question.

Answer 2

Ký hiệu O không thực sự là một phần của chương trình. Nó thực sự đo lường cách thức mà thời gian chạy tăng khi kích thước đầu vào tăng lên. Trong trường hợp này, phần tiêu tốn thời gian là phần cuối cùng khác.

Bạn cần tìm hiểu cách thức hoạt động của chương trình này. Đây là một phân tích thực nghiệm đơn giản sẽ giúp bạn. Nếu chúng ta thiết kế chương trình một chút để in ra bao nhiêu lần phần cuối cùng else chạy cho một đầu vào nhất định, chúng ta có được điều này.

n | times 
-----+----- 
    2 | 1 
    4 | 2 
    8 | 3 
    16 | 4 
    32 | 5 
    64 | 6 
128 | 7 
256 | 8 
512 | 9 
1024 | 10 
2048 | 11 
4096 | 12 
8192 | 13 

Nếu bạn vẽ đồ thị này, bạn sẽ thấy một cái gì đó như thế này.

Bạn có thể thấy rằng khi kích thước của sự gia tăng đầu vào, số lượng cuộc gọi cũng tăng nhưng phụ tuyến tính.Như một vấn đề của thực tế, nó là logarit kể từ khi n của bạn giảm 50% mỗi lần lặp của vòng lặp.