运行时分析 [英] Runtime analysis

问题描述

int i, j;

for(i=0; i<n*n; i++) 
{
    if(i % n == 0)
        for(j=0; j<n; j++)
             x++;
    else 
        x--;
}

我是运行时分析的新手，所以我只是在这里检查我的答案，看看我是否有正确的主意.

I'm new to runtime analysis so I'm just checking my answer on here to see if I have the right idea.

我必须找到该段的严格的运行时边界并给出理由.

I have to find a tight runtime bound for that segment and give a reasoning.

我想出了O(n²).

我背后的原因是因为它第一次运行for for循环n²次.如果i被n整除，则仅运行第二个for循环.

My reasoning behind it is because it runs the first for loop n² times. It only runs the second for loop if i is divisible by n.

这还好吗?或者我在分析中完全错了吗?

Is this okay or am I completely wrong in my analysis?

推荐答案

外部循环运行n²次.每运行 n 次(因此总共运行n次)，就会启动另一个循环，该循环运行 n 次.这等于n²+ n * n ，等于2n²，它是O(n²)的运行时间.

The outer loop runs n² times. Every n-th run (so n runs in total), it starts another loop, which runs n times. That amounts to n² + n * n which equals 2n² which is a runtime of O(n²).

这篇关于运行时分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！