[关闭]
@waterdkx 2016-03-06T08:32:03.000000Z 字数 2480 阅读 1300

夯实基础 -- 算法的时间复杂度

       大一的时候因为转专业的缘故,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))。

Demo

  1. public void demo(int n) {
  2. int num1 = 0;
  3. int num2 = 0;
  4. for (int i = 0; i < n; i++) {
  5. num1 += 1;
  6. for (int j = 1; j <= n; j *= 2) {
  7. num2 += num1;
  8. }
  9. }
  10. }

分析

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中的关键行是:

  1. num2 += num1;

       一般也是最内层的循环语句执行次数最多。
       继续以上面的demo为例来分析:

  1. num2 += num1;

一些补充说明

最坏时间复杂度
       算法的时间复杂度不仅与语句频度有关,还与问题规模及输入实例中各元素的取值有关。一般如果不作特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。这就保证了算法的实际运行时间不会比估算的更长。

常见排序算法时间复杂度一览表

排序法 最差时间分析 平均时间复杂度 稳定性 空间复杂度
冒泡排序 稳定
快速排序 不稳定
选择排序 稳定
二叉树排序 不一定
插入排序 稳定
堆排序 不稳定

算法稳定性
       稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的,当有两个相等键值的纪录R和S,且在原本的列表中R出现在S之前,在排序过的列表中R也将会是在S之前。

空间复杂度
       算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。


参考文章

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注