工夫复杂度：顾名思义，工夫上来讲就是耗时水平，耗时少：工夫复杂度低；反之则高。
那么对于程序而言呢，最直观的办法就是把程序跑一遍，看下运行工夫，然而这里有一个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