125-C语言算法分析之时间复杂度和空间复杂度
1.时间复杂度
时间复杂度:算法中基本操作重复执行的次数和问题规模n所呈现的函数关系。记作O(f(n))
时间复杂度的要求: ①只保留高阶项
②不要系数
③常数项的时间复杂度为O(1),常数项:和问题规模n没有关系
for(int i = 0;i < n;i++)//1
{
for(int j = 0;j < n;j++)//2
{
c[i][j] = 0;//3
}
}
f(n) = (1) + (2) + (3) =n + (n+n+n+…+n) + (n+n+n+…+n) =2n^2+n
O(f(n)) = O(2n^2+n) = O(2n^2) = O(n^2)
技巧:只求最内层循环语句的时间复杂度即可,因为外层语句的执行次数肯定没有内层语句的执行次数多
for(int i = 0;i
共有 0 条评论