大O表示法是什么？

目录

• 一，算法的目标
• 二，算法的执行时间
• 三，时间复杂度和大O表示法
• 四，几个例子
• 五，拓展

　　称一个函数g(n)是O(f(n))，当且仅当存在常数c>0和n0>=0，对一切n>n0均有|g(n)|<=c|f(n)|成立，也称函数g(n)以f(n)为界或者称g(n)囿于f(n)。记作g(n)=O(f(n))。

　　定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数。T(n)称为这一算法的"时间复杂度"。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的"渐近时间复杂度"。

　　我们常用大O表示法表示时间复杂度，注意它是某一个算法的时间复杂度。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。此外，一个问题本身也有它的复杂度，如果某个算法的复杂度到达了这个问题复杂度的下界，那就称这样的算法是最佳算法。

　　通常我们需要一种方法来对不同的算法来进行比较，一般来说，解决同样的问题有多种算法，那么在不同的客观条件下如何对不同的算法进行取舍呢？

一，算法的目标

编辑本段

　　1，容易理解，编码和调试

　　优秀的算法通常是简洁而清晰的，这样带来的直接好处就是易于编码和理解，同时这样算法也必定是健壮的，如果一个算法晦涩难懂，则很可能其中会隐藏较多的错误。

　　2，最小的代价

　　算法的代价的最小化是指其执行时间最短且占用的存储空间最少，它们之间 往往是相互矛盾的，然而一般而言，算法的执行时间是主要的评价标准。

二，算法的执行时间

编辑本段

　　算法的执行时间等于它所有基本操作执行时间之和， 而一条基本操作的执行时间等于它执行的次数和每一次执行的时间的积，

　　如下：

　　算法的执行时间 ＝ 操作1 ＋ 操作2 ＋ ... + 操作n

　　操作的执行时间 ＝ 操作执行次数 X 执行一次的时间

　　然而存在一个问题，不同的编程语言，不同的编译器，或不同的CPU等因素将导致执行一次操作的时间各不相同，这样的结果会使算法的比较产生歧义， 于是我们假定所有计算机执行相同的一次基本操作所需时间相同，而把算法中基本操作所执行的最大次数作为量度。就是说我们把算法的执行时间简单地用基本操作的执行次数来代替了。

　　那么除此之外，基本操作是什么？ 它可以是基本运算，赋值，比较，交换等，如在排序中，基本操作指的是元素的比较及交换。而在线性查找中，它是数据的比较。

三，时间复杂度和大O表示法

编辑本段

　　当问题规模即要处理的数据增长时， 基本操作要重复执行的次数必定也会增长， 那么我们关心地是这个执行次数以什么样的数量级增长。所谓数量级可以理解为增长率。这个所谓的数量级就称为算法的渐近时间复杂度(asymptotic time complexity)， 简称为时间复杂度。如何分析这个数量级呢？ 由于基本操作的执行次数是问题规模n 的一个函数T(n)， 所以问题就是我们要确定这个函数T(n)是什么， 然后分析它的数量级， 拥有相同数量级的函数 f(n) 的集合表示为 O(f(n))， O是数量级的标记。如果T(n)的数量级和f(n)相同，

　　显然T(n) ∈ Of(n)。这个函数的值表示当我要处理的数据量增长时，基本操作执行次数以什么样的比例增长。即n增长时，T(n)增长多少？

四，几个例子

编辑本段

　　比如说一个冒泡排序的算法, 假如有10个数，第一次循环比较9次，第二次循环比较8次，以此类推，一共

　　循环9次，那么总次数为 9＋8＋7＋6＋5＋4＋3＋2＋1 等于45次，则对于N个数来说， 总比较次数为 N(N-1)/2 次，

　　可见得对于N个数来说， 它的比较次数的数量级已达到N的平方， 即 T = N(N-1)/2 ，则我们说它的比较操作的

　　时间复杂度为 O(n2) (n的平方）。

　　另外对于一个数组的线性查找呢？ 很显然， 在最坏的情况下，10个数要比较10次，那么对于N个数来说，

　　要比较N次， 平均 N/2 次， 即 T = N/2 ， 它的数量级是一次的，则我们说这个线性查找的时间复杂度是线性的，

　　即 O(n).

五，拓展

编辑本段

　　定义一：Θ(g(n))={f(n) | 如果存在正常数c1、c2和正整数n0，使得当n>=n0时，0<c1g(n)<=f(n)<=c2g(n)恒成立}

　　定义二：Ο(g(n))={f(n) | 如果存在正常数c和正整数n0，使得当n>=n0时，0<=f(n)<=cg(n)恒成立}

　　定义三：Ω(g(n))={f(n) | 如果存在正常数c和正整数n0，使得当n>=n0时，0<=cg(n)<=f(n)恒成立}