複雜的嵌套用於從最後一次迭代

function solution(A) { 
    var len = A.length; 
    cnt = 0; 
    for(i = 0; i < len - 1; i++){ 
     for (a = i + 1; a < len; a++){ 
      if (A[i] == A[a]){cnt++;} 
      else{continue;} 
     } 
     if(cnt > 1000000000){return 1000000000;} 
    } 
    return cnt; 
}

開始循環因此，這是用於計數對相同的陣列的代碼，我知道2 for循環給時間複雜度O（N 2 ）。情況總是如此嗎？即使下一次迭代只經過數組的剩餘部分？複雜的嵌套用於從最後一次迭代

來源

2016-12-01 Aram Yeghiazaryan

看看這裏：[鏈接]（HTTP：/ /stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop）重複 – guymaor86

是的，事情是我不從一開始就遍歷列表，就像在你建議的鏈接中，我迭代n-1第二次的時間等等，這是否意味着我獲得相同的複雜性？ –

我發佈的鏈接幾乎與鏡像相同。仔細看一下，你就會得到它。但無論如何，同樣的複雜性。 1 + 2 + 3 + .. + n =（n^2 + n）/ 2，即O（n^2） – guymaor86

是的，這將是大約O（1/2N^2），但因爲常數是不是真的那麼重要，這將最終成爲爲O（n^2）

來源

2016-12-02 18:26:47 Jay

複雜的嵌套用於從最後一次迭代

回答

相關問題