@waterdkx
2016-03-06T16:32:03.000000Z
字数 2480
阅读 2265
大一的时候因为转专业的缘故,C语言还没学过就开始跟着上数据结构的课,完全一头雾水。所以算法相关的知识点一直都是我不愿多提的短板。
现在已经是一个职业的程序员了,在解决了碰到的各式各样的问题后,越来越相信,想要在这个行业有长远的发展并小有成就,夯实基础知识是不能绕过的一个环节。之前一段时间对算法,对Linux,对三方库的源码之类的偏底层一点的东西都会有点恐惧感,但是慢慢的在工作中接触到了这些东西,觉得自己可以拿下,而且很有必要将其逐一拿下。所以,今天就从算法的时间复杂度开始下手,夯实基础,补回之前错过的。让自己的底盘更稳一点,才能走的更远。
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.The time complexity of an algorithm is commonly expressed using big O notation, which excludes coefficients and lower order terms. When expressed this way, the time complexity is said to be described asymptotically, i.e., as the input size goes to infinity.
结合wiki的翻译,我的理解是这样的:
在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。它的作用就如同一个返回输入的字符串参数的长度的函数。时间复杂度常用大写英文字母‘O’表述,表述时会忽略这个函数的低阶项和首项系数。使用这种方式时,时间复杂度其实是一个渐进值,它考察的是当输入值大小趋近于无穷时的情况。
还有一个更数学公式化的版本:
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
1. 计算出基本操作的执行次数T(n)
基本操作即算法中的每条语句(以;号作为分割),语句的执行次数也叫做语句的频度。在做算法分析时,一般默认为考虑最坏的情况。
2. 计算出T(n)的数量级
求T(n)的数量级,只要将T(n)进行如下一些操作:
- 忽略常量、低次幂和最高次幂的系数
- 令f(n)=T(n)的数量级。
3. 用大‘O’来表示时间复杂度
当n趋近于无穷大时,如果lim(T(n)/f(n))的值为不等于0的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。
public void demo(int n) {
int num1 = 0;
int num2 = 0;
for (int i = 0; i < n; i++) {
num1 += 1;
for (int j = 1; j <= n; j *= 2) {
num2 += num1;
}
}
}
分析:
1.计算出基本操作的执行次数T(n)
语句:“int num1 = 0;int num2 = 0;int i = 0;”的频度都是1.
语句:“i < n;i++;num1 += 1;j=1;”的频度都为n.
语句:“j <= n; j *= 2; num2 += num1;”的频度为n *
2.计算出T(n)的数量级
忽略掉T(n)中的常量、低次幂和最高次幂的系数
3. 用大O来表示时间复杂度
当n趋向于无穷大,1/n趋向于0,1/ 趋向于0。所以极限等于3。
简化的计算步骤
仔细分析一下,决定算法时间复杂度的其实是最执行次数最多的语句。这个demo中的关键行是:
num2 += num1;
一般也是最内层的循环语句执行次数最多。
继续以上面的demo为例来分析:
num2 += num1;
计算T(n)数量级
用大O来表示时间复杂度
最坏时间复杂度
算法的时间复杂度不仅与语句频度有关,还与问题规模及输入实例中各元素的取值有关。一般如果不作特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的实际运行时间不会比估算的更长。
常见排序算法时间复杂度一览表
排序法 | 最差时间分析 | 平均时间复杂度 | 稳定性 | 空间复杂度 |
---|---|---|---|---|
冒泡排序 | 稳定 | |||
快速排序 | 不稳定 | |||
选择排序 | 稳定 | |||
二叉树排序 | 不一定 | |||
插入排序 | 稳定 | |||
堆排序 | 不稳定 |
算法稳定性
稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的,当有两个相等键值的纪录R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前。
空间复杂度
算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。