来源：http://clarkluo2004.blog.163.com/blog/static/32973801200845115213422/
算法的运行时间通常与下列函数成比例：
| 1 | 大部分程序的大部分指令之执行一次，或者最多几次。如果一个程序的所有指令都具有这样的性质，我们说这个程序的执行时间是常数。 |
| logN | 如果一个程序的运行时间是对数级的，则随着N的增大程序会渐渐慢下来，如果一个程序将一个大的问题分解成一系列更小的问题，每一步都将问题的规 模缩减成几分之一，一般就会出现这样的运行时间函数。在我们所关心的范围内，可以认为运行时间小于一个大的常数。对数的基数会影响这个常数，但改变不会太 大：当N=1000时，如果基数是10，logN等于3；如果基数是2，logN约等于10.当N=1 00 000，logN只是前值的两倍。当N时原来的两倍，logN只增长了一个常数因子：仅当从N增长到N平方时，logN才会增长到原来的两倍。 |
| N | 如果程序的运行时间的线性的，很可能是这样的情况：对每个输入的元素都做了少量的处理。当N=1 000 000时，运行时间大概也就是这个数值；当N增长到原来的两倍时，运行时间大概也增长到原来的两倍。如果一个算法必须处理N个输入（或者产生N个输出）， 那么这种情况是最优的。 |
| NlogN | 如果某个算法将问题分解成更小的子问题，独立地解决各个子问题，最后将结果综合起来，运行时间一般就是NlogN。我们找不到一个更好的形容， 就暂且将这样的算法运行时间叫做NlogN。当N=1 000 000时，NlogN大约是20 000 000。当N增长到原来的两倍，运行时间超过原来的两倍，但超过不是太多。 |
| N平方 |
如果一个算法的运行时间是二次的（quadratic），那么它一般只能用于一些规模较小的问题。这样的运行时间通常存在于需要处理每一对输入 数据项的算法（在程序中很可能表现为一个嵌套循环）中，当N=1000时，运行时间是1 000 000；如果N增长到原来的两倍，则运行时间将增长到原来的四倍。 |
| N三次方 | 类似的，如果一个算法需要处理输入数据想的三元组（很可能表现为三重嵌套循环），其运行时间一般就是三次的，只能用于一些规模较小的问题。当N=100时，运行时间就是1 000 000；如果N增长到原来的两倍，运行时间将会增长到原来的八倍。 |
| 2的N次方 | 如果一个算法的运行时间是指数级的（exponential），一般它很难在实践中使用，即使这样的算法通常是对问题的直接求解。当N=20时，运行时间是1 000 000；如果增长到原来的两倍时，运行时间将是原时间的平方！ |
log log N 可以看作是一个常数：即使N很多，两次去对数之后也会变得很小
相关推荐
1. 时间复杂度：时间复杂度是描述算法运行过程中基本操作的执行次数。常用的大O记法表示，如O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)等，分别代表常数时间、对数时间、线性时间、线性对数时间和平方时间。理解这些...
时间复杂度反映了随着输入规模n的增长，算法运行时间的增加速度。 空间复杂度则关注算法在运行过程中所需的内存空间。它通常表示为S(n) = O(f(n))，其中n是问题的规模，f(n)是算法占用存储空间的函数。低空间复杂度...
2. **渐进时间复杂性**是算法运行时间T(n)随输入规模n增长的数量级，用于评估算法的效率。常用大O符号（O-notation）来表示。 五、大O符号的表示方法 - 大O符号描述了算法运行时间的上限，表示T(n)的增长不会超过f...
时间复杂度用来衡量算法运行所需的时间。常用的大O表示法可以表示算法最坏情况下的时间复杂度。 - O(1)：常数时间复杂度，无论输入规模如何，运行时间恒定。 - O(n)：线性时间复杂度，运行时间随输入规模线性增长。...
1. 时间复杂度：衡量算法运行时间与输入大小的关系，如大O表示法（O(1)，O(logn)，O(n)，O(nlogn)，O(n^2)，O(2^n)等）。 2. 空间复杂度：评估算法执行过程中所需的内存资源。 3. 最好、最坏、平均情况分析：考虑...
时间复杂度描述了算法运行所需的基本操作数量与输入规模的关系，常见的有O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)等。空间复杂度则是算法执行过程中所需的存储空间，它影响了算法在有限资源下的可行性。 在这份PPT中...
时间复杂度描述了算法执行所需的基本操作数量与输入规模之间的关系，常见的复杂度表示有O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)等。空间复杂度则是算法运行过程中所占用的内存资源，它对内存有限的系统尤为重要。 ...
线性阶（O(N)）的算法运行时间与输入数据规模成正比；对数阶（O(logN)）、平方阶（O(N^2)）、线性对数阶（O(NlogN)）、指数阶（O(2^N)）等时间复杂度则描述了不同类型的算法随着输入规模增长所呈现的性能变化。空间...
效率和存储量则关注算法运行时间和所需内存。 算法与程序有所不同，程序是算法在特定编程语言中的具体实现，而并非所有程序都符合算法的有穷性条件。问题求解过程通常包括理解问题、设计算法、选择合适的数据结构、...
- **时间复杂度**：衡量算法运行时间随着输入数据量增加的变化趋势。 - 常见的时间复杂度包括O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)等。 - **空间复杂度**：评估算法在执行过程中临时占用存储空间的大小。 - ...
时间复杂度分析帮助我们了解算法执行的时间开销，空间复杂度分析则让我们了解算法运行过程中的内存消耗。这两者共同决定了算法在实际应用中的适用性。通过对复杂度的学习，初学者能够做出更为合理的算法选择，提升...
时间复杂度描述了算法运行时间与输入大小之间的关系，常见的复杂度表示有O(n)，O(nlogn)，O(n^2)等。例如，线性搜索的时间复杂度为O(n)，而二分搜索的时间复杂度为O(logn)。空间复杂度衡量的是算法执行过程中所需的...
时间复杂度表示算法运行时间与输入规模之间的关系，而空间复杂度表示算法执行过程中所需的内存空间。常见的复杂度阶有O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)等。 2. 大O符号：用于描述算法的上界运行时间，不考虑...
2. **时间复杂度**：衡量算法运行速度的重要指标，用大O符号表示，如O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)等。了解不同时间复杂度的含义，能帮助我们判断算法的效率。 3. **空间复杂度**：反映算法运行时所需内存...
- 多项式时间算法：如O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(n^3)等，它们的运行时间随着问题规模的增长呈线性或更低次幂的增长。 - 指数时间算法：如O(2^n)、O(n!)、O(nn)等，当问题规模增大时，运行时间增长...
2. **时间复杂度与空间复杂度**：时间复杂度反映了算法运行时间与输入数据规模之间的关系，而空间复杂度则表示算法执行过程中所需的内存空间。通常，我们希望设计出时间复杂度低、空间复杂度也尽可能小的算法。 3. ...
6. 二分搜索算法的时间复杂度是O(logn)，合并排序的时间复杂度是O(nlogn)，快速排序的平均时间复杂度是O(nlogn)，最坏情况下的时间复杂度是O(n^2)。 ### 动态规划法 1. 动态规划算法是一种算法设计技术，它将一个...
时间复杂度分析是评估算法效率的关键方法，它帮助我们理解算法运行时间随输入规模增长的趋势。 在算法时间复杂度分析中，我们关注算法中基本操作重复执行的次数，这通常是一个与问题规模n相关的函数f(n)。算法的...
常见的时间复杂度有：常数阶 O(1)、对数阶 O(logn)、线性阶 O(n)、线性对数阶 O(nlogn)、平方阶 O(n^2)、立方阶 O(n^3) 等。 五、改进算法的好处 改进算法可以降低时间复杂度，提高算法的效率。例如，求 N ！所...