嵌套的 while 循环怎么可能是 O(n)？

Question

我从网站 www.interviewcake.com 那里获得了这段代码，该网站说它是 O(n)，并且在采访 cake 时要求团队成员澄清，他们证实这是真的。这是代码：

function reverseWords(message) {

  // First we reverse all the characters in the entire message
  reverseCharacters(message, 0, message.length - 1);
  // This gives us the right word order
  // but with each word backward

  // Now we'll make the words forward again
  // by reversing each word's characters

  // We hold the index of the *start* of the current word
  // as we look for the *end* of the current word
  let currentWordStartIndex = 0;
  for (let i = 0; i <= message.length; i++) {

    // Found the end of the current word!
    if (i === message.length || message[i] === ' ') {

      // If we haven't exhausted the string our
      // next word's start is one character ahead
      reverseCharacters(message, currentWordStartIndex, i - 1);
      currentWordStartIndex = i + 1;
    }
  }
}

function reverseCharacters(message, leftIndex, rightIndex) {

  // Walk towards the middle, from both sides
  while (leftIndex < rightIndex) {

    // Swap the left char and right char
    const temp = message[leftIndex];
    message[leftIndex] = message[rightIndex];
    message[rightIndex] = temp;
    leftIndex++;
    rightIndex--;
  }
}

面试cake的组员是这样解释的：

*是的，有一个嵌套循环让它看起来像是 O(n^2)。

但是，在整个问题过程中，我们可以看到我们没有在每个内部循环中反转 O( n ) 个字符……我们只将每个字符正好反转两次。因此，总成本最终为 O(n)。

这是一个棘手的问题，因为您必须查看整个算法中对 reverseCharacters 的所有调用的成本，而不是每次调用本身的成本。*

不过我仍然很困惑，因为我们仍在内部循环中循环遍历每个字符，字符串越大，调用运行所需的时间就越长。

我想将它打开到一个不同的渠道，看看我是否可以获得一些额外的见解，以及为什么它的 O(n) 而不是 O(n)^2。

为了完全清楚，我想解释为什么上面提供的代码中的 reverseWords 函数是 O(n) 而不是 O(n)^2

Answer 1

据我在该代码中所知，外循环的工作是查找每个单词的结尾。一旦找到一个（并且只有在那时），就会调用 reverseCharacters() 来反转该单词中的字符。所以两个任务的大O加在一起（O（n）+ O（n）= O（2n），仍然认为是O（n）），而不是相乘（O（n）* O (n) = O(n^2)) 正如您通常期望它们在嵌套循环中所做的那样。

Answer 2

这确实是O(n)。

混淆来自于 reverseCharacters() 在内循环中调用的事实。但是，请注意何时调用它。

让我们看一下字符串中的任意字符，看看它出现的频率 "touched"。对于某些 i.

，让我们的角色位于索引 i

reverseCharacters() 在内循环中，输入字符串中的每个单词被调用一次。字符 i 正好出现在一个单词中。

这意味着，这段代码的实际复杂度是：

T(n) = O(n       //    First reverseCharacters()
         +  n    // looping through all characters
         + l1    // reverseCharacters() on the first word
         + l2    // reverseCharacters() on the second word
         + ...   // and so on ...
         + lk)   // reverseCharacters() on the k'th (and last) word.

因为 l1 + l2 + ... + lk <= n，这意味着，我们有：

T(n) = O(n + n + l1 + l2 + ... + lk) <= O(n + n + n) = O(n)

嵌套的 while 循环怎么可能是 O(n)？

How can a nested while loop be O(n)?

javascript

big-o

nested-loops