复杂的嵌套用于从最后一次迭代

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

复杂的嵌套用于从最后一次迭代

回答

相关问题