算法的复杂度
- 算法的复杂度: 算法的时间复杂度和空间复杂度合称为算法的复杂度,一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。
- 用于描述时间复杂度&空间复杂度的公式关键字 Big-O
- 时间复杂度:执行程序所需的时间。可以估算出程序对处理器的使用程度。一般用内层代码语句执行次数来统计
- 空间复杂度:执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度,就是在运行过程中临时占用存储空间的大小。
Big O
所有的复杂度:O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)
1、不变复杂性
|
|
- 2、对数复杂度
|
|
- 3、线性复杂度
|
|
4、二次型复杂度
123456O(n 2):称为二次型复杂度1项:1秒10个项目:100秒100个项目:10000秒注意物品的数量增加了10倍,但时间增加了10 2倍。基本上,n = 10,所以O(n 2)给出我们的比例因子n 2,它是10 2。5.还有立方阶,阶乘等等…
详细解释
1.时间频度: 一个算法执行所耗费的时间,理论是不能算出来的,通常时间复杂度均是++最坏++情况下的时间复杂度。这时候只需要去关注++内层代码语句++的执行次数,或者哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数叫时间频度。记为T(n)。
2.时间复杂度:
算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度,简称时间复杂度。- 3.空间复杂度:一个程序的空间复杂度是指运行完一个程序所需内存的大小。程序执行时所需存储空间包括以下两部分。 (1)固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。(2)可变空间,这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)),其中n为问题的规模,S(n)表示空间复杂度
如何计算一个算法的时间复杂度
- 1、不变复杂性123void print(String str) {Log.d("message",str); // 需要执行 1 次}
这个算法的时间复杂度T(n) = O(1),不管传入任何参数,代码只执行一遍
- 2、线性复杂度12345void print(int n) {for(int i = 0; i < n; i++) { // 需要执行 (n + 1) 次Log.d("message",i); // 需要执行 n 次}}
此时代码执行次数= n+1 +n = 2n + 1,那么当n无限大的时候 时间复杂度T(n) = O(n)
- 3、平方阶复杂度
|
|
此时代码执行的次数为 n + 1+ nxn + nxn = 2n2 + n + 1 ,那么当n无限大的时候时间复杂度T(n) = O(n2)
- 4、等等依次类推。空间复杂度也是如此。
总结
放图