算法的时间复杂度（王道笔记） |
您所在的位置：网站首页 › 排序时间复杂度口诀 › 算法的时间复杂度（王道笔记） |
|
首先解释下时间复杂度为什么得在运行前估计，主要原因有以下几点：
大家的机器性能不同，同样的程序不同机器跑出来时间不一样使用的编程语言不同，往往越高级的语言效率越低，例如Java效率就要比C低，因为Java是更高级的语言和编译程序产生的机器指令质量有关有些事情是不能去事后统计的，例如重要军事的精确测量
我们估算法的时间复杂度，事实上是要探求算法时间开销T(n)与问题规模(n)的关系—>T=T(n)
举个栗子
//算法一
void loveyou(int n){ //n为问题规模
int i = 1;
while(i
loveyou(3000);
}
依次看各个语句的执次数 int i = 1 —>1次 while(i3001次 i++,printf(“I Love You %d\n”,i)—>3000次 printf(“I Love You More Than %d\n”,n);—>1次 共计=T(3000)=1+3001+23000+1=33000+3 将3000换成n，则T(n)=3n+3 这是一个非常简单的表达式，但当我们遇到更复杂的表达式，例如： T1(n)=n²+3n+1000 T2(n)=n³ + n²+999999999 这些表达式就相对来说复杂了，那我们可以只保留更高阶的部分来代替整个表达式吗？ 答案是可以只考虑阶数高的部分,并把系数化为1，在前面套一个大O，因为和只保留高阶的表达式对比，它们最终计算结果是相近的。 总的来说，我们只需要用一个数量级来表示算法的时间复杂度就可以了，这里用大O表示法 —>T(n)=O(n), T(n)=O(n²), T(n)=O(n³) 规则1.加法规则 多项相加时，只保留最高阶的项，且系数变为1 2.乘法规则 多项相乘，都保留 eg:T3(n)=n³+n²log₂n = O(n³) + O(n²log₂n) 这里就需要考虑谁的数量级更大就保留谁 给出常见的阶数顺序O(1) i=i*2; printf("I Love You %d\n",i); } printf("I Love You More Than %d\n",n); } 这里每执行一次循环，i会翻倍(2->4->8->…) 设最深层循环的语句频度（总共循环的次数）为x，则由循环条件可知，循环结束时刚好满足2^x>n x = log₂n+1 根据加法规则，T(n) = O(log₂n) void loveyou(int flag[], int n){ //n为问题规模 printf("I Am Iron Man\n"); for(int i = 0;i //找到元素n printf("I Love You %d\n",n); break; //找到后立即跳出循环 } } } //flag数组中乱序存放了1~n这些数 int flag[n] = {1,...n}; loveyou(flag,n);对于这个问题来说，有不同的情况 1.最好情况：n在第一个位置 —最好时间复杂度T(n)= O(1) 2.最坏情况：n在最后一个位置 —最坏时间复杂度T(n)= O(n) 3.平均情况：假设n在任意一个位置的概率相同为1/n —平均时间复杂度T(n)= O(n) 循环次数x = (1+2+3+…+n)/n=(1+n)/2 T(n)=O(x)=O(n) 很多算法执行时间与输入数据有关一般来说，我们只考虑最坏时间复杂度以及平均时间复杂度 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |