Làm thế nào để tính toán độ phức tạp của một hàm đệ quy?

Question

Cách trực quan nhất để tính độ phức tạp về thời gian và không gian (ký hiệu Big O) của hàm đệ quy sau đây là gì?

function count(str) { 
    if (str.length <= 1) { 
    return 1; 
    } 

    var firstTwoDigits = parseInt(str.slice(0, 2), 10); 

    if (firstTwoDigits <= 26) { 
    return count(str.slice(1)) + 
      count(str.slice(2)); 
    } 

    return count(str.slice(1)); 
} 

Answer 1

Xin lỗi cho câu trả lời trước của tôi, phức tạp của mã của bạn có vẻ là

O (2^N) hoặc O (2^N-1) để được chính xác trong trường hợp xấu nhất .

Vì vậy, Nếu

N = str.length ;//number of iteration 

Trong trường hợp xấu nhất, bạn str bao gồm tất cả các chữ số N hoặc là 1 hoặc 2.

Sau đó, Nếu N là 20 để bắt đầu với, sau đó nó sẽ đẻ trứng nhiều hơn hai cuộc gọi đệ quy của N = 18 và N = 19,

Sau đó, N = 19 sẽ sinh ra hai cuộc gọi nữa (và vì vậy một cho đến giá trị của N là 0)

Vì vậy, số lượng cuộc gọi sẽ tăng theo cấp số nhân với mỗi lần lặp), do đó đến giá trị (2^N - 1).