Độ phức tạp về thời gian của hàm

Question

Tôi đang cố gắng tìm ra độ phức tạp về thời gian (Big-O) của các hàm và cố gắng cung cấp lý do thích hợp.

chức năng đầu tiên đi:

r = 0 
# Assignment is constant time. Executed once. O(1) 
for i in range(n): 
    for j in range(i+1,n): 
     for k in range(i,j): 
      r += 1 
      # Assignment and access are O(1). Executed n^3 

như thế này.

Tôi thấy rằng đây là vòng lặp lồng nhau ba lần, vì vậy nó phải là O (n^3). nhưng tôi nghĩ lý do của tôi ở đây rất yếu. Tôi không thực sự có được những gì đang xảy ở bên trong vòng lặp lồng nhau triple đây

chức năng thứ hai là:

i = n 
# Assignment is constant time. Executed once. O(1) 
while i>0: 
    k = 2 + 2 
    i = i // 2 
    # i is reduced by the equation above per iteration. 
    # so the assignment and access which are O(1) is executed 
    # log n times ?? 

tôi phát hiện ra thuật toán này là O (1). Nhưng giống như chức năng đầu tiên, Tôi không thấy điều gì đang xảy ra trong vòng lặp while.

Ai đó có thể giải thích kỹ về độ phức tạp của hai hàm ? Cảm ơn!

Answer 1

Trước tiên, đối với hàm đầu tiên, độ phức tạp thời gian dường như gần với O (N log N) vì các tham số của mỗi vòng lặp giảm mỗi lần.

Ngoài ra, đối với hàm thứ hai, thời gian chạy là O (log2 N). Ngoại trừ, nói i == n == 2. Sau một lần chạy i là 1. Sau một i khác là 0,5. Sau một i khác là 0,25. Và cứ thế ... Tôi cho rằng bạn sẽ muốn int (i).

Để có cách tiếp cận toán học nghiêm ngặt đối với từng chức năng, bạn có thể truy cập https://www.coursera.org/course/algo. Đó là một khóa học tuyệt vời cho loại điều này. Tôi đã khá cẩu thả trong tính toán của tôi.

Answer 2

Đối với một trường hợp đơn giản như vậy, bạn có thể find the number of iterations of the innermost loop as a function of n exactly:

sum_(i=0)^(n-1)(sum_(j=i+1)^(n-1)(sum_(k=i)^(j-1) 1)) = 1/6 n (n^2-1) 

ví dụ: Θ(n**3) thời gian phức tạp (see Big Theta): nó giả định rằng r += 1 là O (1) nếu r có O(log n) chữ số (model has words with log n bits).

Vòng lặp thứ hai thậm chí còn đơn giản hơn: i //= 2 là i >>= 1. n có Θ(log n) chữ số và mỗi lần lặp xuống một chữ số nhị phân (shift bên phải) và do đó toàn bộ vòng lặp là Θ(log n) thời gian phức tạp nếu chúng ta giả định rằng sự thay đổi i >> 1 của log(n) chữ số là O (1) hoạt động (giống mô hình như trong ví dụ đầu tiên).