跳到主要内容

README

算法复杂度​

时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的使用程度。 空间复杂度：评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。

大O表示法​

一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。 若有某个辅助函数f(n)，使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，它称为算法的渐进时间复杂度，简称时间复杂度。

算法复杂度可以从最理想情况、平均情况和最坏情况三个角度来评估，由于平均情况大多和最坏情况持平，而且评估最坏情况也可以避免后顾之忧，因此一般情况下，我们设计算法时都要直接估算最坏情况的复杂度。大O表示法O(f(n)中的f(n)的值可以为1、n、logn、n²等，因此我们可以将O(1)、O(n)、O(logn)、O(n²)分别可以称为常数阶、线性阶、对数阶和平方阶

推导大O阶​

  • 1.用常数1来取代运行时间中所有加法常数。
  • 2.修改后的运行次数函数中，只保留最高阶项
  • 3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。

常见的大O计算​

运行的次数的函数为f(n)=3，根据推导大O阶的规则1，我们需要将常数3改为1，则这个算法的时间复杂度为O(1)。

如果let y = x*x*x 执行10次，还是O(1)，因为和x这个问题规模没有联系

function(x){
    let y = x*x*x // 执行一次
    let sum = y+x // 执行两次
    console.log(sum) // 三次
}

线性阶​

现在修改一下 代码循环执行了x次，每一次都执行了3步，那么f(n) = 3n, 根据第三条法则：如果最高阶项存在且不是1，则去除与这个项相乘的常数。 那么时间复杂度为O(n)。

function(x){
    for(int i=0;i<x;i++){
        let y = x*x*x // 执行一次
        let sum = y+x // 执行两次
        console.log(sum) // 三次
    }
}

对数阶O(logn)​

由2^x=n得出x=log₂n，因此得出这个算法的时间复杂度为O(logn)。

int number=1;
while(number<n){
number=number*2;
//时间复杂度为O(1)的算法
...
}

平方阶O(n²)​

  for(int i=0;i<n;i++){   
      for(int j=0;j<n;i++){
         //复杂度为O(1)的算法
         ... 
      }
  }

nlogn阶(在排序中常见)​

比如归并排序算法：归并排序可算是排序算法中的佼佼者。假设数组长度为 n，那么拆分数组共需 logn 步, 又每步都是一个普通的合并子数组的过程，与数组的规模n是有关的，不一定就是n(如最后一步好像是n/2)，但根据高阶项存在且不是1，则去除与这个项相乘的常数，时间复杂度为 O(n)，故其综合时间复杂度为 O(nlogn)