while循环的大O表示法

Question

前几天我为我的作业提出了这个问题，但我仍然不确定我是否正确。

for(int i =1; i <n; i++)   //n is some size
{             
    for(j=1; j<i; j++)
    {
        int k=1;

        while (k<n)
        {
           k=k+C;   //where C is a constant and >=2
        }
    }
}

我知道嵌套的for循环是O(n^2)，但是对于while循环，我不确定。我假设整个代码的时间复杂度为O(n^3)。

- user977151

---

你是不是在 for 循环中想说 i<n 和 j<n 呢？否则该函数的时间复杂度为 O(1)。 - DeCaf

@DeCaf 我猜那是个打字错误。 - Foo Bah

请修复问题中的拼写错误并保持格式一致。 - user166390

抱歉，原始代码是伪代码，我不得不将其重写为Java。 - user977151

Answer 1

    int k=1;

    while (k<n){
       k=k+C                    //where C is a constant and >=2
    }

这需要 (n-1)/C 步骤：设 u = (k-1)/C，然后 k = Cu + 1，语句变为

u=0;
while(u < (n-1)/C) {
    u=u+1
}

因此，while循环的时间复杂度为O(n)（因为C是常数）。

编辑：让我尝试另一种解释方式。

从一个虚拟变量u开始。循环如下：

u=0;
while(u < MAX) {
    u = u+1
}

运行MAX次。

当你让MAX = (n-1) / C时，循环就是这样的：

u=0;
while(u < (n-1)/C) {
    u=u+1
}

这将运行(n-1)/C次。

现在，检查u < (n-1)/C等同于C*u < n-1或C*u + 1 < n，因此循环等同于：

u=0;
while(C*u + 1 < n) {
    u=u+1
}

现在，假设我们用变量 k = C * u + 1来重写这个循环。那么，

u=0;
k=1; // C * 0 + 1 = 1

循环看起来像这样：

while(C*u + 1 < n) {
while(k < n) {

内部条件为

    u=u+1
    k=k+C //C * (u+1) + 1 = C * u + 1 + C = old_k + C 

将所有内容结合在一起：

将所有内容结合在一起：

    int k=1;

    while (k<n){
       k=k+C
    }

takes (n-1)/C steps.

- Foo Bah

---

我很困惑你为什么加了“u”。你能详细解释一下吗？ - user977151

@user977151 最简单的事情就是一步一步地向上走。我尝试着将分析倒过来做。 - Foo Bah

Answer 2

内部循环实际上是 O(n/C)=O(n)，因此总体而言它是 O(n^3)（第二个循环的上限为 O(n)）

- Blindy

Answer 3

正式来说，您可以使用以下方法（Σ符号表示法）继续：

其中a代表内部循环中的常数操作次数（如果你想计算精确迭代次数，则a = 1）。

- Mohamed Ennahdi El Idrissi

---

很遗憾，我的公司代理完全封锁了imgur.com :| - wonko realtime

你能否“解释LaTeX代码”(http://www.codecogs.com/latex/eqneditor.php)？我可以与你分享这个脚本。 - Mohamed Ennahdi El Idrissi

目前无法在SO上找到相关引用。我个人认为这会很酷（而且Latex甚至可以被索引，而图片则不行），但我不确定其他人是否会欣赏它，因为它可能会让你的帖子读者感到困惑，这取决于你如何添加它，所以我会在家里观察一下。[也许有人应该向SO提出一些将Latex集成到html渲染器中的建议（https://dev59.com/NXVD5IYBdhLWcg3wBWzd）] - wonko realtime

你能看到这个网站生成的内容吗：http://www.codecogs.com/latex/eqneditor.php？ - Mohamed Ennahdi El Idrissi

消息的大小超出了评论中允许的字符数。您有电子邮件地址吗？ - Mohamed Ennahdi El Idrissi

请勿发布电子邮件 :) 您可以发布到http://pastebin.com/，然后在此处发布链接 - wonko realtime

Answer 4

好的，您需要查看在给定n和C的情况下while循环体运行的次数。例如，n为10，C为3。该循环体将运行3次：k = 1，k = 4，k = 7。对于n = 100和C = 2，该循环体将运行50次：k = 1,3,5,7,9,...,91,93,95,97,99。这是通过C计数直到n的问题。您应该能够从这个线索中计算出Big-O复杂度。

- Konstantin Tarashchanskiy

---

我不喜欢你对无限序列的计数方法（顺便说一下，这就是渐近的意思）……一个简单的“循环次数随着n线性增长，速率为1/2”会更容易理解，也更准确。 - Blindy