问题:
1 + 2 + 3 + ...... + 100 = ?
算法1:
int sum=0;
int n=100;
for(int i=1;i<=n;i++){
sum += i;
}
System.out.println(sum);
算法2:
int sum=0;
int n=100;
sum=(1 + n)*n/2;
System.out.println(sum);
影响算法效率的因素:
1.算法的内容
2.编译的质量 依赖编译器
3.问题的规模
4.机器执行指令的速度 依赖硬件
可控的影响因素:
算法 规模
算法1 n
算法2 n
一个算法的执行数量 f(n) 是n的一个函数
一个算法的时间复杂度 O(f(n)) 是执行数量经过一个规则得到的结果
执行数量计算时间复杂度的规则:
取最高项 影响f(n)数值变化的最主要因素
去掉常量 随着n的增长,该值可忽略
去掉最高项的系数 随着n的增长,该值可忽略
去掉低次项 随着n的增长,该值可忽略
没有最高项,值为常量1
3 --> O(1)
n --> O(n)
2n+1 --> O(n)
n^2 + 3n + 1 --> O(n^2)
log2 n --> O(log n)
算法1的时间复杂度:O(n)
算法2的时间复杂度:O(1)
int x = 0;
int sum = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
x++;
sum += x;
}
}
f(n) = n * n;
时间复杂度:O(n^2)
int x = 0;
int sum = 0;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
x++;
sum += x;
}
}
f(n) = n + (n-1) + (n-2) + ...... +1 = (n + 1) * n / 2 = n^2/2 + n/2;
时间复杂度为:O(n2)
效率:
O(1) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(n^3) < O(n!) ......
从f(n)转O(n)比较简单,问题是怎么计算f(n),需要数学的知识。
相关推荐
关于算法时间复杂度的计算 关于算法时间复杂度的计算 关于算法时间复杂度的计算
算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典
算法时间复杂度
算法时间复杂度分析基础算法时间复杂度分析基础算法时间复杂度分析基础
大学二年级课程 算法设计与分析的一般算法时间复杂度的证明过程,希望可以帮到大家.
对若干个数据进行操作,实现快速排序、选择排序、直接插入排序、堆排序算法时间复杂度的比较;并在排序数据中快速查找某一数据,给出查找是否成功,以及数据所在的位置信息。
排序算法时间复杂度的研究 期刊网站可是要现金的哦。
关于递归算法时间复杂度分析的探讨.pdf
根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
常见算法的时间复杂度计算方法. 定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。
所有算法时间复杂度对比、图表形式、函数关系
算法时间复杂度分析中递归方程求解方法综述
以堆排序算法为例,改变输入规模n,测试算法时间复杂度
选择排序、冒泡排序、归并排序、快速排序、插入排序的算法原理。不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
对算法分析与设计课程的实验报告,对算法里面的时间复杂度,和增长率有很好的研究。
多段图算法时间复杂度图像
平衡二叉树时间复杂度计算1
这是数据结构算法课程中算复杂度的作业及答案。
数据结构时间复杂度