算法速度比较--大O表示法

~

当我们比较两个算法的速度时，想到的最直接方法就是比较两个算法完成同一个任务所用的时间。运行时间快的是快速算法，时间慢的是慢速算法。这个方法看似合理，实则有诸多问题：1、使用不同算力的计算机会影响运行时间，超级计算机执行一个加法运算只需10 ^-9 s，而普通计算机则需要10 ^-5 s。2、任务的复杂程度与运行时间并不是线性的关系，一个简单任务可能算法A运行时间短，一个复杂任务可能算法B运行时间短。
用什么评价方法才合理呢？这里引入了大O表示法，它指出了算法有多快。例如，假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间表示为O(n)。并没有时间单位s，这是因为大O法指的并非以秒为单位的速度。大O表示法让你能够比较操作次数，它表示出了算法运行时间的增速。如果换用二分法检查长为n的列表，二分查找需要执行log n次操作。使用大O表示法这个的运行时间则为O(log n)。

大O表示法指出了最糟糕情况下的运行时间。假设你查找电话簿中的A，如果A在电话簿第一位，一次就找到了，这是最佳的情形，但大O表示法说的是最糟糕的情形。因此，你可以说，在最糟糕的的情况下，必须查看电话簿中的每一个条目，对应的运行时间为O(n)。这是一个保证——你知道简单查找的运行时间不可能超过O(n)。

下面按从快到慢的顺序列出经常会遇到的5种大O运行时间：
O(log n)，也叫对数时间，这样的算法包括二分查找；
O(n)，也叫线性时间，这样的算法包括简单查找；
O(n*log n)，这样的算法包括快速排序，一种速度较快的排序算法；
O(n ² )，这样的算法包括选择排序，一种速度较慢的排序算法；
O(n!)，这样的算法包括旅行商问题的解决方案，一种非常慢的的算法。

1、《算法图解》
2、《生物信息学算法导论》

---

晋源区18972504012： 大O表示法的计算过程 - ？
烛石永颖： 1和3本来就一样么..居然还有这么恶心的公式..c和n0是随便找的,只要能找到就行 最简单的判断复杂度的方法就是:对于任何表达式,先合并同类项,然后取含n的最高阶的项,去掉常数 比如2中,n的最高阶的项就是6*2^n,去掉常数就是2^n 一般地,排序算法最快是O(nlog2(n)),折半查找是O(log2(n))

晋源区18972504012： 求时间复杂度,在线等,最好有公式推导. - ？
烛石永颖： 一、概念 时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数) 比如:一般总运算次数表达式类似于这样:a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f a ! =0时,时间复杂度就是O(2^n); a=0,b<>0 =>O(n^3); a,b=0,c<>0 =>O(n^2)...

晋源区18972504012： 数据结构 数量级怎么计算与表示 O代表什么 - ？
烛石永颖： O可考虑为order的首字母缩写,相应有大O表示法.它们通常出现在程序设计与计算相关描述里面,把整个程序重复执行次数之和记为T(n),称为时间复杂度,其中n为求解问题涉及的数据个数或称为问题规模.当n足够大时,不同求解算法将会导致显著差异的T(n).为此,定义O()来描述T(n)的数量级,用以评估不同算法的效率.需要强调的是,时间复杂度T(n)一般并不对应真实的程序执行时间.

晋源区18972504012： 算法时间复杂度的表示法O(n²)、O(n)、O(1)、O(nlogn)等是什么意思? - ？
烛石永颖： O(n²)表示关于n的2阶无穷小量.当n线性增长时,计算量按n²规律增大.O(1)表示计算量不变.其它类似

晋源区18972504012： c语言中的大O表示法是什么,怎么算啊 - ？
烛石永颖： 大O表示法?抄 似乎不袭是C语言的 而是数据结构2113与算法分析5261中的 用于表示4102复杂度的1653上限 参见 http://baike.baidu.com/view/807818.htm

晋源区18972504012： 算法的时间复杂度？
烛石永颖： 你好,我是一位做ACM的.对于算法的复杂度.我们常常用一个函数O来表示. 举个例子,我们执行下面的程序 int i,sum=0; for(i=1;i<=n;i++)sum=sum+i; 这个是很简单的求和程序,初看一下,貌似只是执行了n次计算 但是其实很明显在for循...

晋源区18972504012： Ω 和∞谁大? - ？
烛石永颖： 在数学中,Ω(大欧米伽)和∞(无穷大)都表示无穷大的概念,但它们的含义和用法有所不同.Ω表示一个渐近下界,用于描述一个函数增长的速度.它表示函数的增长率至少是指定的函数.例如,f(n) = Ω(g(n)) 表示当n趋近于无穷大时,函数f(n)的增长率至少和函数g(n)相同或更快.∞表示无限大,是一个数学概念,表示没有上限或趋近于无穷大.它表示没有限制,可以越来越大,无法用具体的数值表示.因此,从定义上来说,∞是更大的概念,表示无限大,而Ω表示函数的增长下界,是一个相对更小的概念.(求采纳)

晋源区18972504012： 指出下面算法的时间复杂度?(用大O表示法) - ？
烛石永颖： o(n^3)

晋源区18972504012： 时间复杂度 T(n)=O(f(n)),的 O什么意思 - ？
烛石永颖： O(n)这个大O表示的是最坏情况下的时间复杂度,就比如你举的例子,一共n^3次乘法和n^3次加法,那么加起来就是2*n^3.然后如果有一个表达式f(n),使得n趋于无穷大的时候,lim(2*n^3)/f(n)=常数c,那么就可以用大O表示.表示为O(f(n)),而且规定f(n)的表达式是不带常数的系数的,那么在这里f(n)=n^3.一般用大O表示算法复杂度只需要取次数最高的项,而且去掉系数就OK了,不用每次都这么算的.三重循环而且每重循环都执行n次的话直接O(n^3)就好了.