这些循环的执行时间？

Question

我正在备考，我们有一些练习题。直到实际考试前两个小时才会给出模拟考试的答案，所以我无法确定我是否真的理解这些概念。问题和我的工作如下。

以下嵌套循环的最坏情况执行时间：

for(int i = 0; i < n - 1; i++)
{
    for(int j = 0; j < n - i - 1; j++)
    {
        do some comparisons. (this is just O(1))
    }
}

外循环有n-1次迭代，我不确定内循环，因为它依赖于i。当 i 为 0 时，内循环有 n-1 次迭代，当 i 为 1 时，内循环有 n-2 次迭代。我对这个算法的最坏情况执行时间的回答是 O(n^2)，这是正确的吗？

int n = arr.length
bar(arr); //function bar takes O(n^2)
while(n > 0)
    foo1(arr); //function foo1 takes O(n)
    foo2(arr); //function foo2 takes O(n log n)
    n = n -2;

在这种情况下，while 循环迭代 n/2 次（n 每次迭代减少 2）。因为 foo1 和 foo2 都在循环中，所以它们共同占用 O(n^2*log n)。循环外的函数 bar 采用 O(n^2)，因此这三个函数共同采用 O(n^2*log n + n^2)（不包括 while 循环）。我不确定在这种情况下如何包含 while 循环，它会乘以两个内部函数还是相加？

Answer 1

第一个是正确的。 O(n^2)。对于第二个，从技术上讲，foo1 的运行时间与 foo2 相比并不重要，因为 n 的大小变得非常大。这是一个简单的极限比较，因为 n 接近无穷大。 while 循环将是 O(n^2*log n) 因为正如你所说它是 n/2 迭代所以 n/2 * n log n 给你 n^2 log n 就像之前的 1/2当 n 变得非常大时，它不是一个重要的常数。当 n 变得非常大时，采用 O(n^2) 的 bar 函数对于 O(n^2*log n) 也将是微不足道的。所以第二个问题的运行时间是 O(n^2*log n).

即使是你最后的猜测。如果比较这两项，当 n 接近非常大的数字时，n^2*log n 的增长速度将比 n^2 快得多。所以你会得到相同的结论。

Answer 2

在您的第一个问题中，您应该注意到外部循环确实有一个运行时间的 O(n)；这使得嵌套循环运行-time 成为以下内容的总和：
```
(n-1) + (n-2) + ... + (1)
```
等差数列的和为：
```
S = (a1 + an)*(n/2) = (n-1+1)*(n-1) = n^2 - n = O(n^2)
```
因此总运行时间确实是 O(n^2)
根据定义，如果存在常数c使得T(n) <= c * f(n)，从某个[开始，T(n)可以描述为O(f(n)) =18=] 等等。因此，"faster-growing" 函数确定 f(n).

你的情况：
```
n^2*log(n) + n^2 = n^2 * (log(n) + 1) <= c * n^2 * log(n)
```
(因为n趋于无穷大，所以很容易找到满足c >= 1 + (1/log(n))的c的值)

这些循环的执行时间？

Execution time of these loops?

big-o

execution-time