算法的时间复杂度

文章目录[隐藏]

算法的工夫与空间复杂度

算法的工夫与空间复杂度

预先分析法

毛病：不同的数据规模，不同的机器下算法运行的工夫不同，无奈做到计算运行工夫

事先分析法

大O工夫复杂度

渐进工夫复杂度随着n的增长，程序运行工夫追随n变动的趋势

几个准则

去掉常数项

2(n^2) =n^2

一段代码取工夫复杂度最高的

test(n) {
  //工夫复杂度n^3
 for(int i = 0; i < n ; i++){
   for(int i = 0; i < n ; i++){
     for(int i = 0; i < n ; i++){
            print(n);
     }
   }
 }
 //工夫复杂度n^2
 for(int i = 0; i < n ; i++){
   for(int i = 0; i < n ; i++){
     print(n);
   }
 }
 //工夫复杂度n
 for(int i = 0; i < n ; i++){
   print(n);
 }
}

这段代码的工夫复杂度为n^3+n^2+n

当n足够大时，n^2和n与n^3相比太小，能够忽略不计

常见复杂度

o(1)

<code class="java">i = i + 1;</code>


o(n)
test(n){
  for(int i = 0 ;i < n;i++){
    print(i);
  }
}
o(n^2)

test(n){
  for(int i = 0 ;i < n;i++){
    print(i);
    for(int j = 0 ;j < n;j++){
      print(i);
    }
  }
}
o(log2n)
PS:如果ax =N（a>0，且a≠1），那么数x叫做以a为底N的对数，记作x=logaN，读作以a为底N的，其中a叫做对数的底数，N叫做真数。
test(n) {
  int i = 1;
  while (i <= n) {
    i = 2 * i;
  }
}
随着循环次数的减少，i的值变动如下
依据对数函数的公式 2的i次方等于n,i等于log2n
最好状况工夫复杂度
数据比拟有序的状况的工夫复杂度
最坏状况工夫复杂度
数据齐全无序
空间复杂度
与n无关的代码空间复杂度能够疏忽
空间复杂度O(n)
test(n) {
  //在内存中开拓了一个长度为n的数组
  List array  =  List(n);
  print(array.length);
}

搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]‍，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：算法的时间复杂度