讨论/题目交流/新手求代码的平均时间复杂度/
新手求代码的平均时间复杂度
 // array表示一个长度为n的数组
 // 代码中的array.length就等于n
 int[] array = new int[n];
 int count = 0;
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

请问这段代码的平均时间复杂度是多少啊?

11n+1+11n+1+11n+1+...+11n+1+n1n+1=O(1)1* {1 \over n+1} +1* {1 \over n+1} +1* {1 \over n+1} +...+1* {1 \over n+1} +n* {1 \over n+1} = O(1)

为什么这里O(n)等与O(1)啊。。。真的想了好久,最后算出来不是2nn+12n \over n+1么?这代码规模跟n有关系不能忽略啊。。。。。。。。。Orz

展开讨论
共 1 个讨论

2n/n+1,上下的数量级为n,可以看成2n/n=2,时间复杂度是常数级,所以为O(1)。