PDF《数据结构与算法（DSA）》

3 2,003 10,000 2(10,000) +

3 20,003 信不信由你,当n足够大以后,常数 k 的大小对函数的结果影响力也会越 来越小,所以,表达式:k(n) + c,使用渐进分析我们只取高阶元素:n 让我们再来分析一个例子,这样我们就能把这个概念弄清楚.假设我们有 表达式:3n?+2n+20,使用渐近分析的结果是什么? 3n? + 2n +

20 当n越来越大的时候,它的结果和 n?的值越来越接近,所以使用渐进分 析取高阶元素:n? 回到我们的例子 getMin(),我们可以说这个函数的时间复杂度是: n,正如 你所到的,我们可以把它近似为 2(n)然后去掉+3,因为随着 n 越来越大,它不 会增加太多的值 我们只对高阶数据感兴趣,有了这个概念,比较算法就容易多了;

我们可以 用这些术语来比较运行时间:

1、n、n?、或2^n 大O表示法和函数增长率 大写 O 符号结合了我们在前面几节中学到的有关最坏时间复杂性和渐近分 析的知识 字母 o 指的是函数的指令(Order) 大写 O 表示法用算法的最差情况时间复杂度(或者函数增长率的上限)对 算法的效率进行分类,也成为函增长的上限.前面的例子 getMin()函数,我们可 以说它的时间复杂度是:O(n) 让我们看看下最常见的时间复杂度(也可叫做运行时间)以及它们与时间的关 系 增长率与 n 的大小: 假设: CPU @ 1.0GHz,它可以平均

1 纳秒执行一条指令(通常需要更多时间).另外请记住,根 据编程语言的不同,每一行代码都可能被翻译成数十条 CPU 指令 可以看到,有些算法非常耗时.输入的大小只有 100,即使我们有一个 1phz(100 万GHz)的CPU,一辈子也不可能计算出来,硬件不像软件那样能无 限扩展 在下一篇文章中,我们将通过一些代码示例来探讨上图包含的这些时间的 复杂性!你准备好了吗? 每个开发者都应该知道的

8 种时间复杂度 摘要 我们将学习一些顶级算法的时间复杂度,每个开发人员都应该熟悉它.了 解这些算法的时间复杂度将帮助您评估您的代码是否有拓展和优化的空间.同样,对于相同的问题比较不同的解决方案也是很方便的,因为你能根据时间复杂 度很快找出最优解决方案 回顾上文时间复杂度,估计算法执行的效率.可以通过计算代码执行的基 本操作的数量来获得时间复杂度.大O表示法根据算法的运行时间或空间(使 用的内存)对算法进行分类.O 是指输入参数为 n 的函数的增长率 这里有一个时间复杂度表格和我们将要在这篇文章中介绍的例子 Big O Notation Name Example(s) O(1) Constant 判断数字奇偶性, 查找哈希表(一般情况) O(log n) Logarithmic 在有序数组中查找元素(使用二分查找) O(n) Linear 查找数组中最大元素,用哈希映射在数组中复制元素 O(n log n) Linearithmic 归并排序 O(n2 ) Quadratic 查看数组中是否有重复项 ,冒泡排序 O(n3 ) Cubic

3 变量方程求解 Big O Notation Name Example(s) O(2n ) Exponential 查找数组子集 O(n!) Factorial 查找字符串所有子项的排列组合 O(1)时间复杂度 O(1)时间复杂度描述的算法是指:不管输入的元素大小如何,结果花费相同 的时间来计算 例如,如果一个函数处理

10 个元素和

100 万个条目的时间相同,那么我 们说它有一个恒定的增长率或 O(1)时间复杂度,让我们看看一些例子 判断数字奇偶性 给出一个数字,判断它是奇数还是偶数: 1. function isEvenOrOdd(n) { 2. return n %

2 ? '