360浏览器打不开90设计网站,网站建设前景展望,wordpress站群管理破解版,成都电商网站建设基本操作数 算法的运行速度受计算机性能的影响#xff0c;所以通常考虑算法效率的不是算法运行的实际用时#xff0c;而是算法运行所需要进行的基本操作的数量。 像加减乘除、访问变量、给变量赋值等都可以看作基本操作。对基本操作的计数或是估测可以作为评判算法用时的指标…基本操作数 算法的运行速度受计算机性能的影响所以通常考虑算法效率的不是算法运行的实际用时而是算法运行所需要进行的基本操作的数量。 像加减乘除、访问变量、给变量赋值等都可以看作基本操作。对基本操作的计数或是估测可以作为评判算法用时的指标。
时间复杂度 在算法竞赛中我们衡量一个算法的效率时最重要的不是看它在某个数据规模下的用时而是看它的用时随数据规模而增长的趋势即 时间复杂度。 时间复杂度是指算法运行时间与问题规模之间的关系通常用大 O 表示法来表示。 常见的时间复杂度有O(1), O(logn), On, O(nlogn), O(n^2 ), O(2^n)等其中 O(1) 表示算法的运行时间不随问题规模变化而改变而O(2^n ) 则表示算法的运行时间随问题规模n呈指数级增长。 变化趋势意味着我们不用纠结于具体的操作次数和n之间的精确对应关系也就是不用看具体的函数的参数是什么而只用看随着数据范围的增大操作次数的变化是属于哪一类函数。 例如是常数还是线性的还是对数的还是nlogn的还是n^2的还是2^n的还是阶乘n!的。原因是当n变得非常大的时候这些不同类型的函数之间的差异值才是明显的而同一种类型之间的参数不同带来的差异就显得微不足道了可以忽略不计。这也是为什么O(1)和O(3) 都被称作 O(1)。
例子
for (int i 1; i n; i)
{j i;j;
} 这段代码的时间复杂度O(n)的。分析代码的执行次数第1行中i1执行1次 in和i分别执行n次第2行、第3行分别执行n次所以这段代码总共执行4n1次。从这个结果可以看出这个算法的耗时是随着n的变化而变化。如果n无限大的时候14n 中的常量1就没有意义了倍数4的意义也不大。因此时间复杂度直接简化为O(n)。
计算次数 O(n)、O(logn)、O(n)、O(nlogn)随着n的增加复杂度提升不大因此这些复杂度属于效率高的算法反观O(2^n)和O(n!)当n增加到50时复杂度就突破十位数了这种效率极差的复杂度最好不要出现在程序中。tips通常计算机每秒可以计算的次数大约是10的8次方 最坏、最好、平均 在进行时间复杂度分析时需要考虑算法的最好、最坏、平均情况时间复杂度。 最好情况时间复杂度是指算法在最优输入情况下的运行时间复杂度即在所有可能的输入情况中算法所需的最少时间。例如对于二分查找算法来说在目标元素为中间元素的情况下查找时间为 O(1)。 最坏情况时间复杂度是指算法在最劣输入情况下的运行时间复杂度即在所有可能的输入情况中算法所需的最长时间。例如对于冒泡排序算法来说最坏情况是需要 O(n^2) 的时间复杂度。 平均情况时间复杂度是指算法在所有可能输入情况下的平均运行时间复杂度。对于某些算法来说平均情况时间复杂度更能反映算法的运行效率例如快速排序算法的平均情况时间复杂度为 O(nlogn)而最坏时间复杂度是 O(n^2)。 我们通常所说的时间复杂度大 O是指算法的最坏时间复杂度。这是因为最坏时间复杂度能够给出算法的最长运行时间可以帮助我们评估算法的性能并预估程序的执行时间。此外最坏时间复杂度也是一种更保守的衡量指标即使算法在最坏情况下表现较好也能够保证算法的性能不会低于最坏时间复杂度。
常见的时间复杂度
常数阶O(1) 代码执行次数是一个常数不随n的变化而变化那这个代码的时间复杂度就都是O(1)如下的代码中虽然含有for循环但循环次数是100次不随问题规模变化而变化因此是常数级O(1)的时间复杂度
for(int i 1; i 100; i)
{cnt i;
}
线性阶O(n) 这段代码for循环里面的代码会执行n遍因此它消耗的时间是随着n的变化而变化的因此这类代码都可以用O(n)来表示它的时间复杂度。
for(int i 1; i n; i)
{cnt i;
}
对数阶O(logn) 同样是for循环但这段代码的时间复杂度是O(logn)因此不能单纯认为for循环就一定是O(n)的。
for(int i 1; i n; i * 2)
{cnt;
}
线性对数阶O(nlogn) 线性对数阶O(nlogn) 其实非常容易理解将时间复杂度为O(logn) 的代码循环n遍的话那么它的时间复杂度就是 n×O(logn)。
就拿上面的代码加一点修改来举例
for(int i 1; i n; i)
{ for(int j 1; j n; j * 2){cnt;}
} 平方阶O(n^2 )
平方阶O(n^2)就更容易理解了如果把O(n)的代码再嵌套循环一遍它的时间复杂度就是 O(n^2) 了。
for(int i 1; i n; i)
{for(int j 1; j n; j){cnt; }
}
阶乘阶O(n!) 指数阶O(2^n)
void f(int n)
{if(n1){return 1;}else{return f(n-1)f(n-2);}
} 彩蛋
#include bits/stdc.h
using namespace std;
int main()
{coutO(1):endl;coutint n100;endl;coutint an;endl;coutendl;coutO(logn):endl;coutwhile(in)endl;cout{endl;cout i*2;endl;cout}endl;coutendl;coutO(n):endl;coutfor(int i1;in;i)endl;cout{endl;cout cout1;endl;cout}endl;coutendl;coutO(nlogn)(logn重复n遍):endl;coutfor(int i 1; i n; i)endl;cout{endl; cout for(int j 1; j n; j * 2)endl;cout {endl;cout cnt;endl;cout }endl;cout}endl;coutendl;coutO(n*n):endl;coutfor(int i1;in;i)endl;cout{endl;cout for(int j1;jn;j)endl;cout {endl;cout cout1;endl;cout }endl;cout}endl;coutendl;coutO(2^n):endl;coutvoid f(int n)endl;cout{endl;cout if(n1)endl;cout {endl;cout return 1;endl;cout }endl;cout elseendl;cout {endl;cout return f(n-1)f(n-2);endl;cout }endl;cout}endl;return 0;
}
learn more!!!
Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) ericdrowell
