以下循環的時間複雜度是多少

Question

for (int i=0; i<N; i++) 
for (int j=i; j<N; j++) 
    fun1(i,j); 

上面是一個嵌套for循環。第一個for循環從0到N，第二個for循環從i到N.上述代碼的時間複雜度是多少？

編輯：fun1是o（1）

Answer 1

O（n2 * O（fun））。很明顯，答案取決於樂趣的複雜性。

編輯：正如樂趣（）= O（1），複雜度循環的複雜性是O（N²）

Answer 2

內循環體執行N + (N - 1) + (N - 2) + ... + 3 + 2 + 1倍

和N + (N - 1) + (N - 2) + ... + 3 + 2 + 1 <= N * N因此循環體將運行的次數增長O(n^2)

代碼的總時間增長將取決於fun1()的複雜性。如果fun1()有時間的增長O(fun1)然後fun1()執行O(N^2)倍答案是：O(n^2 * O (fun1()))

編輯

正如你所編輯的fun1()是O(1)所以總的複雜性是O(n^2 * O (fun1())) = O(n^2)

Answer 3

由於fun1()是恆定時間，循環的複雜性是 O(N^2)

Answer 4

循環次數爲1 + 2 + 3 + ... + N，即N *（N + 1）/ 2 = N^2/2 + N/2。因此，時間複雜度爲O（N^2/2 + N/2）= O（N^2）

Answer 5

外部for循環將運行內部for循環N次。

inner for循環會在外循環的第一個循環中調用fun1（i，j）N次。然後在外循環的第二個循環中進行（N-1）次。然後，當fun1（i，j）僅運行一次時，一直到外部循環的第N個循環（i = N-1），然後是（N-2）次，然後是（N-3）次等。所以我們在內部循環的每次迭代中運行fun1（i，j）平均N/2次。因此假設fun1（i，j）的複雜度爲O（fun1（i，j）），我們得到的總複雜度爲 O（n *（n/2）* O（fun1（i，j） ）））= O（n^2/2 * O（fun1（i，j））） 但是，由於我們可以忽略數值常數的大值N來衡量複雜度，因此您的代碼的複雜性順序爲O （N^2 * O（FUN1（I，J）））

由於FUN1（I，J）爲恆定時間O（FUN1（I，J））= O（1）和複雜性您的代碼將爲O（n^2）

在Selection Sort Algo中可以看到類似的例子。查看選擇排序算法。在這裏，而不是你的fun1（i，j）一個簡單的賦值行'index_of_min = y'被使用，但這就像你的例子，可能會有所幫助。