共计 1657 个字符，预计需要花费 5 分钟才能阅读完成。
工夫复杂度： 顾名思义，工夫上来讲就是耗时水平，耗时少：工夫复杂度低；反之则高。
那么对于程序而言呢，最直观的办法就是把程序跑一遍，看下运行工夫，然而这里有一个 bug，就是运行工夫很依赖运行环境，在两个齐全不同的环境跑进去的程序工夫复杂度可能会相差甚远，由此就呈现了一种评估工夫复杂度的规范，大体晓得该程序的工夫复杂度耗时趋势就能够了，要是有需要取得精确的工夫的话那须要另外测试。
工夫频度： 那么问题来了，拿到一段程序 如何计算它的工夫复杂度呢，通常破费工夫与代码语句执行的次数成正比 => 语句越多，耗时越久。这里把算法中语句执行次数成为工夫频度，记作 T(n)。
渐进工夫复杂度： 上述提到的工夫频度 T(n)，其中 n 代表问题规模，当然随着 n 的 变动 T(n) 也会变动，算法基本操作的反复执行次数为问题规模 n 的某个函数，也就是用工夫频度 T(n) 示意。如果存在某个函数 f(n)，使得当 n 趋于无穷大时，T(n)/f(n) 的极限值是不为零的常数，那么 f(n) 是 T(n) 的同数量级函数，记作 T(n)=O(f(n))，称 O(f(n)) 为算法的渐进工夫复杂度，简称为工夫复杂度。
渐进工夫复杂度用大写 O 示意，所以也称作大 O 表示法。算法的工夫复杂度函数为：T(n)=O(f(n))；
常见的工夫复杂度：O(1) 常数型；O(log n) 对数型，O(n) 线性型，O(nlog n) 线性对数型，O(n2) 平方型，O(n3) 立方型，O(nk)k 次方型，O(2n) 指数型。
实例：
常数阶 O(1)
仅仅是一行定义，没有循环等简单的构造，那工夫复杂度就是 O(1)。
int x = 1;
或
int x = 1;
int n = 3; 单个语句的频度为 1，没有循环，也就是没有次数的驱动，不会变动，因而算作常数阶，记作 T(n)=O(1)，即便有很多行此类代码，工夫复杂度也不会随着 n 变动而变动的话，那即便程序很长，也只是比拟大的常数而已，此类都记作 O(1)。
对数阶 O(log n)
① int i = 1;
② while(i<=n) {
③ i = i *2 ;
④ } 其中①的频度为 1，②-④为一条语句（while 循环），③每次都乘以 2，当 i 大于 n 的时候就完结，“i=12=2，i=22=4，i=4*2=8“，敌人们这不就是 2 的 x 次方吗，换言之，2 的 x 次方小于等于 n 时会执行循环体，也就是 2X <=n，即 x <=logn(2 疏忽不写)，所以上述程序的工夫复杂度为 O(logn)，所以这就是算程序能执行多少次。
线性阶 O(n)
① int j = 0;
② for (int i=0; i<n;i++) {
③ j = i;
④ j++;
⑤ } 其中 ①的频度为 1，②的频度为 n（因为循环 n 次）③的频度为 n -1（因为到 n 次后间接不走循环体了）④的频度为 n -1。所有频度加起来后：1+n+(n-1)+(n-1)=3n-1，O(n)=3n-1，因为当 n 无穷大后，常数就没有存在的必要了，去掉低次幂和系数即 O(n)=n, 即 T(n)=O(n)。此类算法都能够用 O(n) 来示意，因为 for 循环的代码会执行 n 遍，耗费的工夫是随着 n 的变动而成线性变动的。
线性对数阶 O(nlog n)
① for (int m = 1; m < n; m++) {
② int i = 1;
③ while (i <= n) {
④ i = i * 2;
⑤ }
⑥ } 看到后果就晓得线性对数阶和对数阶有关系，首先①的频度为 n，②的频度为 n -1，③-⑥的频度为 log n, 在③-⑥上套一层循环不就是 nlogn？其实是 n（n-1+logn）=>n2 -n+nlogn，其中后面的加减都能够去掉，T(n)=O(nlogn)
平方阶 O(n2)
① int k = 0;
② for (int i = 0; i < n; i++) {③ for (int j = 0; j < n; j++) {
④ k++;
⑤ }
⑥} 平方阶可参照线性阶了解，线性阶是一层 for 循环，这边多了一层，显然是 O(n2)
如果外层循环的变量改为别的数字，比方 m，工夫复杂度便为 O(m*n)，触类旁通嘛。
同理，立方阶 O(n³)、K 次方阶 O(n^k)，就是嵌套了 3 层，k 层循环。
参考：https://cloud.tencent.com/dev…
后续会再批改，暂且保留下 hhh
