[Java基础] 关于大O复杂度
文章目录
最近在慢慢把自己本地的文档总结到我的blog, 这是很久以前写的一篇文档, 正好再次复习一遍基础知识.
概念
公式是:
T(n)=O(f(n))n: 变量n - 数据规模 <br/>
f(n): 执行次数和数据规模的关系<br/>
T(n): 执行时间和数据规模的关系<br/>
此中的函数表示的都是关系
demo
1 public int sum(int arg){
2 int sum = 0; <--unit time
3 int i = 0; <--unit time
4 for (;i<arg;i++){ <--n*unit time
5 sum = sum + i; <--n*unit time
6 }
7 return sum;
}其中的函数关系为:
n=arg
f(n)=ut*2+n*ut*2最后
f(n)=2+2n当n趋近于无穷,常数项和系数可以忽略,可得
f(n)=n即,Tn=On, 行话说就是,Tn与n成正比
知识点
量级及量级间比较
常量阶: O(1)
- 表示时间不随n的变化而变化,行话为 - 与数据规模无关
按量级递增排序:
常量阶O(1)) < 对数阶O(logn) < 线性阶O(n) < 线性对数阶O(nlogn) < 平方阶O(n²)...立方阶O(n³)...k方阶 < 指数阶O({\color{Orange} 2^{n}}{\color{Orange} }) < 阶乘阶O(n!)
加法法则
即函数几个部分的复杂度加在一起,只取最大项
- 比如: T(n) = O(1)+O(n)+O(n²)=O(n²)
乘法法则
- 嵌套代码复杂度等于内外代码复杂度乘积
- 没什么意义,直接相乘就可以
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论