当前位置 博文首页 > 吴成伟的博客:一文读懂之时间复杂度和空间复杂度
考量一个算法的优劣的标准
两个维度:
1、时间维度:时间复杂度:算法执行消耗的时间
2、空间维度:空间复杂度:算法消耗的内存(一般都是S(n) = O(1))
时间复杂度
求法:以时间频度(一个算法的核心代码的具体的执行的次数的表达式)为基础,去掉低阶项,只保留最高阶项,去掉最高阶的系数。
例:
//核心代码的具体的执行的次数
static void test(int n){
for (int i = 0; i < 2n+1 ; i++) {
for (int j = 0; j < n+3 ; j++) {
System.out.println("TestTime.test");
}
}
}
第1步:时间频度:T(n)=(2n+1)(n+3)=2n^2+7n+3
第2步:时间复杂度T(n)=O(n^2)
常见时间复杂度
1、常数阶:T(n) = O(1)
随着算法规模(自变量n)的变化,执行次数固定。
2、对数阶:T(n) = O(log2n)
3、线性阶:T(n) = O(n) T(n) =Kn+b
4、平方阶:T(n) = O(n2)
5:立方阶: T(n) = O(n3)
6:阶乘阶:T(n) = O(n!)