时间复杂程度

首先我们看看啥是时间复杂程度

一般情况下,算法中基本操作重复执行的时间是问题规模 的某个函数 ,算法的渐进时间复杂度(简称时间复杂度(Time Complexity))记为

它表示随问题规模 的增大,算法执行时间的增长率和 的增长率相同, 一般是算法中频度最大的语句频度。

例如
#define n 自然数
void Matrixmlt(int A[n][n],int B[n][n],int C[n][n])
{
int i,j,k;
for(i=0;i<n;i++) //语句① n+1
for(j=0;j<n;j++) //语句② n(n+1)
{
C[i][j]=0; //语句③ n*n
for(k=0;k<n;k++) //语句④ n*n(n+1)
C[i][j]=C[i][j]+A[i][k]*B[k][j]; //语句⑤ n*n*n
}
}

算法 Matrixmlt 的时间复杂度是T(n)=O(n3),这里的f(n)=n是该算法中语句⑤的频度。

由此可见,当有循环嵌套时,算法的时间复杂度是由最内层语句的频度 决定的

上题

计算以下程序段的时间复杂度

for(i=1;i<=n;i++)
{
s=0;
j=1;
while(s<=n)
{
j++;
s=s+j;
}
}

由上述知识我们可以知道,这里计算时间复杂度是计算最内层的 循环的频度

外层 循环结束的条件是 ,所以外层循环

内层 循环结束条件是 ,巧妙就巧妙在这个 这里,我一开始还没发现(其实是太菜了而且有一段时间没有接触C语言了)

即时间复杂度就是 (这里的 是当外层循环到第 次的时候内层 循环次数)

初始值为 每循环一次, 自增并且 ,那么 就可以看作是求所有 循环中 的和

求和公式安排

替换为,求解就是

解方程(时间复杂度不能为负)

则时间复杂度 ,即


陕ICP备2022011813 | 由又拍云提供CDN加速
| 基于 Stellar 主题
十年之约