一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量
时间复杂度:时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的次数。
常见的时间复杂度有:
常数阶O(1),
对数阶O(log2 n),
线性阶O(n),
线性对数阶O(n log2 n),
平方阶O(n^2),
立方阶O(n^3)
k次方阶O(n^K),
指数阶O(2^n)。
随着n的不断增大,时间复杂度不断增大,算法花费时间越多。
通常我们计算时间复杂度都是计算最坏情况
1)如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
var x=1;
while (x <10)
{
x++;
}
2)当有若干个循环语句时,算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
;
}
}
该算法for循环,最外层循环每执行一次,内层循环都要执行n次,执行次数是根据n所决定的,时间复杂度是O(n^2)
3)循环不仅与n有关,还与执行循环所满足的判断条件有关。
var i=0;
while (i < n && arr[i]!=1)
{
i++;
}
在此循环,如果arr[i]不等于1的话,时间复杂度是O(n)。如果arr[i]等于1的话,则循环不能执行,时间复杂度是0。