大 O 表示法——while 循环 + 未指定范围的 for 循环

Question

如何找到此算法的大 O 表示法？

这是我得到的：O(n + logn + 1) 我对我的答案很不确定，因为我只知道如何用 for 循环求时间复杂度。但是这个和我知道的不一样

对于for循环，我知道当给定一个范围时，你可以用求和来计算循环迭代多少次但是没有给定范围，只有索引。

如果有人能帮我算出每行代码的总运行时间，我将不胜感激。

Find Base(N,B)   // N>=1 and B>=2
    index <- 0
    while N > 0 do                              
       A[index] <- N % B         
       N <- N / B                         
       index <- index + 1              O(logn)     
    for j = 0 to index do                
       temp <- A[j]
       A[j] <- A[index – j]
       A[index – j] <- temp
return A

Answer 1

我将在这个答案前加上一个免责声明，即这个答案中绝对没有数学上的严谨性。有时您会运行无法只看一些东西并从中提取有用的运行时间复杂度 - 那就是当您不理会它并继续进行实际的严格数学时。对于我们中的许多人来说，没有必要那么频繁。

如果您想要进行严格的数学分析，请自己进行。

有了这个，让我们继续进行快速而肮脏的渐近运行时间复杂度分析。我们基本上只是计算我们做了多少。

首先确定每个步骤需要多长时间，从最简单的操作开始。大体识别每一个常数时间操作。

对于这个例子，我需要添加一个未说明的假设。随机访问A进行读写是常量时间。显然有一些数据结构会使这个假设无效，所以我们应该清楚这一点。

Find Base(N,B)   // N>=1 and B>=2    
    index <- 0                       // O(1) - assign constant to a local
    while N > 0 do                              
       A[index] <- N % B             // O(1) - calculate division remainder,
                                     //        array random access write
       N <- N / B                    // O(1) - calculate integer division,
                                     //        assign to local
       index <- index + 1            // O(1) - addition,
                                     //        assign to local
    for j = 0 to index do                
       temp <- A[j]                  // O(1) - array random access read,
                                     //        assign to local
       A[j] <- A[index – j]          // O(1) - array random access read,
                                     // O(1)   array random access write
       A[index – j] <- temp          // O(1) - array random access write
return A

我们现在可以加总了。两个循环体运行在常数时间内（又名 O(1)）。接下来是算出每个循环执行了多少次。您必须从最内层的循环开始执行这些操作。当循环没有嵌套时，按任何顺序进行。

我从第二个循环开始。

    for j = 0 to index do                
       \some O(1) operations that don't modify anything that affects the loop condition.

正好运行 index + 1 次，每次做 O(1) 件事。在每一步，我们都可以将其变成 Big-O 运行时间。去掉所有常数因子和非支配项：它是 O(index)。我们仍然需要根据 N 和 B 计算出 index 是什么，所以我们会记住这一点。

第一个循环

    while N > 0 do                              
       A[index] <- N % B         
       N <- N / B                         
       index <- index + 1

我们已经算出整个循环体的复杂度为O(1)。现在我们需要根据N和B知道它执行了多少次。首先确定实际导致它终止的步骤。对循环条件中使用的变量的赋值，以及任何有助于为该赋值计算的值的东西都是相关的。

这一行是N <- N / B。这是将 N 除以 B，并将它的下限分配给 N。我们必须继续这样做，直到 N 为 0（或负数 - 但继续将正数除以正数 > 1 达到 0 而不是负数）。因此对于循环的每次迭代 N 都有值 N、N/B、N/(B^2) 等。所以这是除以 B 直到我们不能再除。所以当 N/(B^t) < 1 时，循环结束。这发生在 N < (B^t) 时。如果这是相等的，那么 t 自然会是 N 的对数（基数 B）。因此，为了得到最接近的整数不等式，我们可以将 floor 加 1，得到 t = floor(log_b(N)) + 1。因此，循环执行 about log_b(N) 次。但是由于我们只关心 Big-O 的渐近复杂性，我们将忽略确切的边界以及它是否比对数多或少一次迭代。我们甚至会忽略对数*的整个底数。这运行s O(log(N)) 次。它每次执行 O(1) 操作，因此将它们相乘我们得到总体 O(log(N))。

总运行时间只是运行两个循环的总和：O(log(N)) + O(index)

回到那个讨厌的地方 index。它从 0 开始，在第一个循环的每次迭代中递增 1。我们确定该循环有 O(log(N)) 次迭代。所以index的值为O(log(N))。所以 O(index) 是 O(log(N))。之前的和现在有一个我们可以忘记的常数因子，所以总数是O(log(N))

运行在您的脑海中整理所有内容并草草记下重要部分的实际过程与我在此处详细介绍的速度相比实际上非常快。虽然相同的基本方法通常应该有效 - 只需计算操作（仔细）。

这里没有提到需要注意的地方。有时循环体可以在每次迭代中执行不同的数量，因此将每次迭代相加并不像这里的乘法那么简单。有时你从中得到线性或几何级数，你需要在快速和肮脏的分析中插入一点实际数学。

* 对数底数之间的转换只是乘以一个常数因子。因为我们忽略了 Big-O 中常量的乘法，所以 O(log(n)) 对于所有对数底都是相同的。

大 O 表示法——while 循环 + 未指定范围的 for 循环

Big O notation -- while loops + for loops with an unspecified range

sorting

algorithm

big-o