算法效率的度量方法:

我们不关心编写程序所用的语言是什么,也不关心这些程序将跑在什么样的计算机上,我们只关心它所实现的算法。

分析程序的运行时间时,最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。

我们在分析一个算法的运行时间时,重要的是把基本操作的数量和输入模式关联起来。

大量图进行说明:

于是我们可以得到这样一个结论,判断一个算法的效率时,函数中常熟和其他次要项常常可以忽略,而更应该关注主项(最高项)的阶数。

注意:判断一个算法好不好,我们只通过少量的数据是不能做出准确判断的,很容易以偏概全。

算法时间复杂度的定义:在进行算法分析时,语句总的执行次数 T(n) 是关于问题规模 n 的函数,进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n) = O(f(n)) 。它表示随问题规模 n 的增大,算法执行时间的增长率和 f(n) 的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中 f(n) 是问题规模 n 的某个函数。

执行次数 == 时间

这样用大写 O() 来体现算法时间复杂度的记法,我们称之为大O记法。

一般情况下,随着输入规模 n 的增大,T(n) 增长最慢的算法为最优算法。

那么如何分析一个算法的时间复杂度呢?即如何推导大O阶呢?我们给大家整理了以下攻略:

  • 用常熟1取代运行时间中的所有加法常数。
  • 在修改后的运行次数函数中,只保留最高阶项。
  • 如果最高阶项存在且不是1,则去除与这个项相乘的常数。
  • 得到的最后结果就是大O阶。

装逼术语:常数阶、线性阶、平方阶、对数阶、nlogn阶、立方阶、指数阶...

常用的时间复杂度所耗费的时间从小到依次是: O(1) < O(logn) < O(n) < O(nlogn)< O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

最坏情况与平均情况

从心理学角度讲,每个人对将来要发生的事情都会有一个预期。譬如看半杯水,有人会说:哇哦,还有半杯哦!但有人就会失望的说:天,只有半杯了。

一般人常出于一种对未来失败的担忧,而在预期的时候趋向做最坏打算。这样,即使最糟糕的结果出现,当事人也有了心理准备,比较容易接受结果,假如结局并未出现最坏的状况,这也会使人更加快乐,瞧,事情发展的还不错嘛!嗯,这是典型的自慰手法。

算法的分析也是类似,我们查找一个有n个随机数字数组的某个数字,最好的情况是第一个数字就是,那么算法的时间复杂度为O(1),但也有可能这个数字在最后一个位置,那么时间复杂度为O(n)。

平均运行时间是期望的运行时间。

最坏运行时间是一种保证。在应用中,这是一种最重要的需求,通常除非特别指定,我们提到的运行时间都是最坏情况的运行时间。