理论基础
- 算法最终要编译成具体的计算机指令
- 每一条指令在具体的计算机, cpu上的运行时间是固定的
- 某一个算法通过统计具体执行了多少条计算机指令就可以推导出算法的复杂度
计算三个算法的时间复杂度
long sum1(int n) //2n+4 ----> O(n)
{
long ret = 0; //1
int* array = (int *)malloc(n*sizeof(int)); //1
int i = 0; //1
for(i=0; i< n; i++) //n
{
array[i] = i+1;
}
for(i=0; i<n; i++) //n
{
ret += array[i];
}
free(array); //1
return ret;
}
long sum2(int n) //n+2 ----> O(n)
{
long ret = 0; //1
int i = 0; //1
for(i=0; i<n; i++) //n
{
ret +=i;
}
return ret;
}
long sum3(int n) //2 O(1)
{
long ret = 0; //1
if(n>0)
{
ret = (1+n)*n / 2; //1
}
return ret;
}
总结:
上面3个算法的时间复杂度分别为: O(n), O(n), O(1)
refer to:
视频: 算法的基本概念和大O表示法 传智扫地僧
