算法复杂度分析
一切都是为了统计代码执行的效率
事后统计法
通过统计、监控,就能得到算法执行的时间和占用的内存大小
大 O 复杂度表示法
随着数据规模的增长,算法的执行时间和空间占用,按照多项式的比例增长
时间复杂度的好坏排序
O(1)(常数阶)< O(logn)(对数阶)< O(n)(线性阶)< O(nlogn)(线性对数阶)< O(n^2)(平方阶)< O(n^3)(立方阶)< O(2^n)(指数阶)< O(n!)(阶乘阶)
常数阶O(1)
int i = 8;
int j = 6;
int sum = i + j;
线性阶O(n)
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
对数阶 O(logn)
i=1;
while (i <= n) {
i = i * 2;
}
线性对数阶O(nlogN)
for(m=1; m<n; m++)
{
i = 1;
while(i<n)
{
i = i * 2;
}
}
O(m+n)、O(m*n)
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
平方阶O(n²)
for(x=1; i<=n; x++)
{
for(i=1; i<=n; i++)
{
j = i;
j++;
}
}
最好最坏复杂度
最好情况时间复杂度就是,在最理想的情况下,执行这段代码的时间复杂度
最坏情况时间复杂度就是,在最糟糕的情况下,执行这段代码的时间复杂度。
空间复杂度
渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系
空间复杂度 O(1)
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
空间复杂度 O(n)
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
微信公众号
