时间复杂度与常见排列算法
![时间复杂度与常见排列算法](https://static001.geekbang.org/infoq/92/92bcd421977da4c97137af019e07f9eb.png)
一、时间复杂度概念
1、时间复杂度概念
提到时间复杂度,第一时间想到的是算法,简单说,算法就是你解决问题的方法,而你用这个方法解决这个问题所执行的语句次数,称为语句频度或者时间频度,记为 T(n)。
什么是时间复杂度,算法中某个函数有 n 次基本操作重复执行,用 T(n)表示。
现在有某个辅助函数 f(n),使得当 n 趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称 f(n)是 T(n)的同数量级函数。
记作 T(n)=O(f(n)),称 O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
通俗一点讲,其实所谓的时间复杂度,就是找了一个同样曲线类型的函数 f(n)来表示这个算法的在 n 不断变大时的趋势 。
当输入量 n 逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性”。
2、计算时间复杂度的方法:
推导大 O 阶,我们可以按照如下的规则来进行推导,得到的结果就是大 O 表示法:
a.用常数 1 来取代运行时间中所有加法常数。
b.修改后的运行次数函数中,只保留最高阶项
c.如果最高阶项存在且不是 1,则去除与这个项相乘的常数。
二、理解
1、常数阶:O(1)的算法是一些运算次数为常数的算法。例如:
上面语句共三条操作,单条操作的频度为 1,即使他有成千上万条操作,也只是个较大常数,这一类的时间复杂度为 O(1)。
上面算法的运行的次数的函数为 f(n)=3,根据推导大 O 阶的规则 1,我们需要将常数 3 改为 1,则这个算法的时间复杂度为 O(1)。
2、线性阶:O(n)的算法是一些线性算法。例如:
上面代码中第一行频度 1,第二行频度为 n,第三行频度为 n,所以 f(n)=n+n+1=2n+1。所以时间复杂度 O(n)。这一类算法中操作次数和 n 正比线性增长。
3、对数阶:O(logn) 一个算法如果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(logn)时间。例如:
上面代码设第三行的频度是 f(n), 则:2^f(n)<=n;f(n)<=log₂n,取最大值 f(n)= log₂n,所以 T(n)=O(log₂n ) 。
4、平方阶:O(n²)(n 的 k 次方的情况)最常见的就是平时的对数组进行排序的各种简单算法都是 O(n²),例如直接插入排序的算法。
第一行频度 1,第二行 n,第三行 n²,第四行 n²,T(n)=2n²+n+1 =O(n²)
5、平方阶:O(n²)
6、时间复杂度按 n 越大算法越复杂来排的话:
常数阶 O(1)、对数阶 O(logn)、线性阶 O(n)、线性对数阶 O(nlogn)、平方阶 O(n²)、立方阶 O(n³)、……k 次方阶 O(n 的 k 次方)、指数阶 O(2 的 n 次方)。
三、其他
1、冒泡程序---平方阶
上面算法的运行的次数函数为 f(n)= (n-1)+(n-2)+(n-3)+(n-4)+...===>等差数列求和===> (n*(n-1))/2 ===>n^2/2-n/2===> f(n)=O(n^2)
2、选择排序
上面算法的运行的次数函数为 f(n)= (n-1)+(n-2)+(n-3)+(n-4)+...===>等差数列求和===> (n*(n-1))/2 ===>n^2/2-n/2===> f(n)=O(n^2)
3、插入排序
上面算法的运行的次数函数为 f(n)= (n-1)+(n-2)+(n-3)+(n-4)+...===>等差数列求和===> (n*(n-1))/2 ===>n^2/2-n/2===> f(n)=O(n^2)
版权声明: 本文为 InfoQ 作者【Changing Lin】的原创文章。
原文链接:【http://xie.infoq.cn/article/8ba65bf3e6486213d684d6c28】。文章转载请联系作者。
评论