以下代碼的時間複雜度是多少？

Question

看來以下代碼的複雜性應該是O（n^2），但它是O（n），怎麼樣？

void fun(int n, int arr[]) 
{ 
    int i = 0, j = 0; 
    for(; i < n; ++i) 
     while(j < n && arr[i] < arr[j]) 
      j++; 
} 

Answer 1

j不重置爲0與外循環的每一次迭代。因此，它只運行到n-1一次，與i一樣。所以你有兩個並行/混合迭代從0到（最多）n-1。

---

在每一步中，程序都會將i加1。該程序在i達到n時終止。 「外環」運行n次。

還有一個關於j的「內循環」。但它所做的只是增加j，直到它達到i（最多，有時它會減少）。 j從未減少。因此，該部分總共最多運行n次（對於「外部循環」的每次迭代不是n次）。

Answer 2

答案是O（n） 由於j的值永遠不會重置爲0，因此外部循環運行'n'次並且內部循環僅在所有迭代中一次運行到'n'。 因此答案是O（n + n）= O（n）。

Answer 3

讓我們考慮最糟糕的情況，while循環執行最大no。的時代。 最初：i=0,j=0 => while循環沒有得到執行，因爲arr[0] = arr[0]即j=0。 第二次迭代：i=1,j=0 => while循環在最壞情況下執行，即j=1。 第三次迭代：i=2,j=1 => while循環再次執行最壞的情況，即j=2。 ... 第n次迭代：i=n-1,j=n-2 => while循環在最壞情況下再次得到執行，即j=n-1。

因此，通過做這個練習，我們可以觀察到，每次j = i-1 除了i=0和j=0或者我們可以說，while循環只是並行運行for循環，因此沒有。 while循環的執行次數等於no。執行for循環。 因此Order = O（n）;

Answer 4

在第一個例子中，由於兩個循環，時間複雜度似乎是O（n^2）。但是，請注意變量j未針對變量i的每個值進行初始化。

因此，內部j ++將最多執行n次。

i循環也運行n次。

因此，整個事情運行O（n）次。

請遵守問題給出的功能及以下功能之間的區別：

void fun(int n, int arr[]) 
       { 
int i = 0, j = 0; 
for(; i < n; ++i) 
{ 
    j = 0; 
    while(j < n && arr[i] < arr[j]) 
     j++; 
} 

}`

還是不相信？

讓我們假設傳遞的數組具有降序的元素。我們將通過代碼幹運行：

   Iteration 1 : i = 0, j = 0. arr[0] < arr[0] is false. So, the 
          inner while loop breaks. 
       Iteration 2: i =1, j = 0. arr[1] < arr[0] is true. j becomes 
       Iteration 3 : i = 1, j = 1. Condition false. We break. Note 
          that j will remain 1 and is not reset back to 0. 
       Iteration 4 : i = 2, j = 1. arr[2] < arr[1]. True. j = 2. 
       Iteration 5 : i = 2, j = 2. Condition false. Break. 
       Iteration 6 : i = 3, j = 2. arr[3] < arr[2]. True. j = 3. 
       Iteration 7 : i = 3, j = 3. Condition false. Break. 

正如您所看到的，內部while循環僅在此情況下運行一次。 所以，總的迭代是2 * N.