Phân tích Big-O với các hàm trong hàm

Question

Tôi đang bối rối về cách Big-O hoạt động khi giao dịch với các hàm trong các hàm (khi phân tích trường hợp xấu nhất). Ví dụ, nếu bạn có một cái gì đó như:

for(int a = 0; a < n; a++) 
{ 
    *some function that runs in O(n*log(n))* 
    for(int b = 0; b < n; b++) 
    { 
     *do something in constant time* 
    } 
} 

Sẽ này toàn bộ khối chạy trong thời gian O (n^2 * log (n)), bởi vì trong những người đầu tiên cho vòng lặp, bạn có một O (n) và một O (n * log (n)), do đó, O (n * log (n)) là lớn hơn, và do đó chúng ta lấy? Hoặc là nó O (n^3 * log (n)) bởi vì bạn có một O (n) và một O (n * log (n)) trong vòng ngoài cho vòng lặp?

Mọi trợ giúp đều được đánh giá cao! Cảm ơn!

Answer 1

Đó là

O(N) * (O(N lg N) + O(N) * O(1)) = O(N) * (O(N lg N) + O(N)) 
           = O(N) * O(N lg N) 
           = O(N^2 lg N) 

Bởi vì bạn có O(N) lặp của một chức năng O(N lg N) và O(N) hoạt động thời gian liên tục. O(N lg N) + O(N) đơn giản hóa thành O(N lg N) vì O(N lg N) > O(N).

Answer 2

Khi tính loại phức tạp này, bạn nên thêm chức năng nội dòng hoặc tuần tự và nhân các chức năng lồng nhau.

Ví dụ, đây sẽ là O(n):

// O(n) + O(n) = O(2n)` which is `O(n)` (as constants are removed) 
for (int i = 0; i < n; i++) 
{ 
    /* something constant */ 
} 
for (int j = 0; j < n; j++) 
{ 
    /* something constant */ 
} 

Nhưng khi các chức năng được lồng nhau, nhân phức tạp của họ:

// O(n) * O(n) = O(n^2) 
for (int i = 0; i < n; i++) 
{ 
    for (int j = 0; j < n; j++) 
    { 
     /* something constant */ 
    } 
} 

dụ của bạn là sự kết hợp - bạn đã có một số hoạt động liên tục lồng vào bên trong một hàm khác.

// this is O(n*logn) + O(n), which is O(n*logn) 
*some function that runs in O(n*log(n))* 
for(int b = 0; b < n; b++) 
{ 
    *do something in constant time* 
} 

// multiplying this complexity by O(n) 
// O(n) * O(n*logn) 
for(int a = 0; a < n; a++) 
{ 
    // your O(n*logn) 
    // your b loop 
}