c++ - 我将如何计算此函数的运行时间？

Question

我有这个用 C++ 编写的函数，我正在尝试计算它的运行时间。我相信运行时是 O(n^2)(我试图解释为什么在代码中使用注释)，但我正在寻找确认。

    void f1(int n)
    {
    int t = sqrt(n);
      for(int i = 0; i < n; i++){              //this outer for loop by itself has a runtime of O(n) but decreases by sqrt(n) every time it goes back to the top
        for(int j = 0; j < n; j++){          //this inner for loop has a run time of O(n) but decreases by sqrt(n) every time it goes back to the top of the function
            // do something O(1)
        }
        n -= t;                             
      }
    }

Answer 1

让我们假设这是 sqrt()来自 cmath标题。该函数返回一个 double 值 t使得 round(t * t) == n .

让我们估计操作次数:

在外循环的第一次迭代中，内循环执行 n迭代。

在外循环的第二次迭代中，内循环执行 n - t迭代，

等等...

外循环的迭代次数介于 t 之间和 t + 1如 t * t可能小于 n .

因此，要计算内循环的总迭代次数，我们必须计算以下总和:

n + (n - t) + (n - 2*t) + ... + (n - t * t) = 
n * t - t * (1 + 2 + ... + t) = 
n * t - t * t * (t + 1) / 2 = 
t * t * t - t * t * (t + 1) / 2 =
t^3/2 - t^2/2  = O(n^(3/2))