我正在参加「启航计划」

时刻杂乱度

前语

咱们在程序开发过程中为了衡量一个算法的好坏制定了两个标准时刻杂乱度和空间杂乱度，由于程序运转的时刻长短和占用内存的巨细直接影响到程序的履行功率。

但咱们需求注意程序运转的时刻长短不仅仅取决于代码，还有运转环境、硬件、数据量等因素影响，什么意思呢？

  • 硬件：当一段相同的代码同时在2C4G和4C8G上的机器运转由于机器计算力不一样，所以程序运转时刻大概率不同（特别是代码计算量大时）。

  • 运转时环境：当一台机器上大部分资源被其它服务所占用，别的一台机器上面没有其它服务，那么一段相同的代码在两个硬件相同机器上履行时刻长短会不一样。

  • 数据量：一段相同的代码定义入参为n（或输入规划），代码片段会循环n次，那么n=1和n=1w履行时刻长度上肯定不一样。

所以说时刻杂乱度并不能直接等于代码运转的时刻长短，这儿的时刻杂乱度指的是代码根本操作履行的次数。

根本操作履行次数

一切事例只考虑首要流程的履行次数

事例一

如存在一个面包长10cm，每2分钟只能吃1cm，那么吃完这个面包需求多长时刻呢？

很明显答案为10*2=20分钟，所以当吃面包的速度不变的情况下面包长n cm那么就需求花费2n的时刻才能吃完面包，这儿可以记作T(n) = 2n。

publicvoidmethod1(intn){
for(inti=0;i<n;i++){
System.out.println("吃一口面包");
System.out.println("吃完了~");
}
}

事例二

假定再存在一个面包长16cm，每过5分钟吃掉该面包的一半，那么面包变为1cm需求花费多长时刻？

这个计算稍微杂乱点，第五分钟吃掉8cm、第十分钟吃掉4cm、第十五分钟吃掉2cm、第二十分钟吃掉第1cm，还剩1cm，便是将面包长度不断的做等分，这便是数学中的对数，这儿答案便是5 * log2(16) = 20，当面包长度为n时这儿可以记作T(n) = 5logn。

publicvoidmethod2(intn){
for(inti=n;i>1;i=i/2){
System.out.println("吃一口面包");
System.out.println("吃一口面包中2");
System.out.println("吃一口面包中3");
System.out.println("吃一口面包中4");
System.out.println("吃完了~");
}
}

事例三

假定存在一个面包长10cm，吃掉第一个1cm需求1分钟，吃掉第二个1cm需求2分钟，吃掉第三个1cm需求3分钟，那么一个面包吃完需求多少分钟呢？

这其实便是1到10的累加，所以当面包长度为n时需求的时刻就可以记作T(n) = (n / 2) * (1+n) ，变化为T(n) = 0.5n + 0.5n^2^。

publicvoidmethod3(intn){
for(inti=0;i<n;i++){
for(intj=0;j<i;j++){
System.out.println("吃一口面包中"+(j+1));
}
System.out.println("吃完了~");
}
}

事例四

假定存在一个鸡腿，吃一个鸡腿需求两分钟那么吃完整个鸡腿需求多长时刻。

这个答案就太简略了两分钟，需求的时刻简略记为T(n) = 2。

渐进时刻杂乱度

到这儿咱们知道了程序根本操作履行的次数，那是不是就直接等于时刻杂乱度了呢？显然也不是，咱们看到除事例四外其他三个都是受输入数字n的影响，所以这儿需求引入渐进时刻杂乱度，也称为大O表明法，来简化时刻杂乱度的表明，大O表明法有如下准则

  1. 假如运转时刻也便是T(n)是常数量级，那么用数字1表明。

  2. 只保存时刻函数中的最高阶项。

  3. 假如最高阶项存在，那么省掉最高阶项前面的系数。

根据这个准则就可以得出前面事例的时刻杂乱度

  • 事例一：运转时刻表明为T(n) = 2n，依照准则3省掉最高阶项前面的系数，时刻杂乱度为O(n)。

  • 事例二：运转时刻表明为T(n) = 5logn，依照准则3省掉最高阶项前面的系数，时刻杂乱度为O(logn)。

  • 事例三：运转时刻表明为T(n) = 0.5n + 0.5n^2^，依照准则2和准则3只取最高阶项和省掉最高阶项前面的系数，时刻杂乱度为O(n^2^)。

  • 事例四：运转时刻表明为T(n) = 2，依照准则1一切常数用数字1表明，时刻杂乱度为O(1)。

不难看出这些时刻杂乱度有如下排序

O(1) < O(logn) < O(n) < O(n^2^)