2021-01-14数据结构00
请注意,本文编写于 684 天前,最后修改于 204 天前,其中某些信息可能已经过时。

目录


时间复杂度(算法)

程序=数据结构+算法

算法是对数据的操作,是解决特定问题求解步骤的描述。

好的算法

  1. 两个算法的数据量(样本量)相同
  2. 假定每条语句的执行时间是相同
  3. 评估算法的语句执行次数相同

如何计算时间复杂度

c
调用func11次,那么函数内的语句会分别执行1次,T(n) = 2 时间复杂度O(1)
int func1(void)
{
    printf("函数1\n");    //执行1次
    return 0;             //执行1次
}

这段代码

c
int func2(int n)
{
   for(int i = 0;i < n;++1)
   {
        printf("函数2\n");
   }
   return 0;
}

解析:
调用1次func2函数
fun2

所以 一共执行了3n+3次语句,所以假设n = 2 的时候,总共执行了3*2+3 = 9次,T(n) = 3n+3

一段代码的总执行次数会用T(n)来表示,n是输入数据的大小或者是输入数据的数量,T是在输入数量为n时,这一段代码的总执行次数。

但是作为衡量代码的执行速度的依据,当代码比较多时,使用T(n)就有些麻烦了,因为还要一条条语句去数。所以算法一般使用T(n)简化的估算值,来衡量代码执行的速度。这个简化的估算值叫做时间复杂度。

T(n)如何得出时间复杂度

T(n) = 常数:
如果T(n)等于一个常数,那么时间复杂度就可以直接估算为1,因此上边例子中的func1的时间复杂度就为1。

T(n) = 常数 x n + 常数:
第一部分:常数 x n

第二部分: 常数
如果常数乘以n再加上常数的话,那我们可以直接去掉加号后边的常数,因为随着n的增大,第一部分越来越大,而第二部分保持不变,也就导致了第二部分相对于第一部分,相当于不存在,所以可以直接省略。
T(n) = 常数 x n + 常数

然后第一部分的常数可以直接估算为1,也可以直接理解为去掉这个作为系数的常数,所以他的时间复杂度就是n,因此上边例子中函数func2的时间复杂度就是n。

因此 对于多项式,我们只需要保留n的次方最大的那一项即可。因为随着n的增大,后面的项的增长远远不如n的最高次项大,所以可以直接省略低次项。
T(n)=5n3+6666n2+233T(n) = 5n^3 + 6666n^2+233

也就是5n35n^3,接着系数5也要去掉,因此时间复杂度就是n^3,实际上这样表示的时间复杂度并不完整,我们还需要加上大写字母O
如:O(n3)O(n^3)

c
void sum(int a[], int n)
{
    int s = 0, i;            //执行次数:2
    for(i = 0;i < n ; i++)   //执行次数:1 + n+1 + n ==> (2n + n)
    {
        s = s + a[i];        //执行次数:n
    }
    printf("%d",s);          //执行次数:1
}
//执行时间 2 + (2n + 2) + n + 1 = 3n + 5; O(n)

常见时间复杂度列表

名称T(n)T(n)常见算法
常数阶O(1)O(1)
对数阶O(logn)O(log n)二分查找
线性阶O(n)O(n)无序数组搜索
线性对数阶O(nlogn)O(n log n)快速排序
平方阶O(n2)O(n^2)冒泡排序
指数阶O(2n)O(2^n)
阶乘O(n!)O(n!)
时间复杂度

本文作者:Na1r

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!