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