c - 如果我对嵌套循环使用相同的变量，时间复杂度是 n 的数量级或 n 的平方

Question

for(i=0;i<n;i++)
{
   for(;arr[i]!=' ';i++)
       {
       //required code
       }
//required code
}

假设我想做一些操作，比如“反转句子中的每个单词(但不是整个句子)。示例:输入:“这是一个球”输出:“sihT si a llab”'。然后肯定在循环内，我会寻找“空格”字符。我想问以下问题:(1)顺便说一句，我用了两个循环，为什么人们说我把程序弄得O(n^2)，不必要地让程序变得更复杂。我知道我可以在外部“for”循环内使用“if”来代替内部“for”。但是，如果我选择这种方式，这怎么可能是 O(n^2)，因为我认为我正在增加同一变量“i”的循环，我认为它是 O(n)。(2)为什么“我写的”(内部 for 循环代替“if”)不被认为是一个好的做法？它与缓存问题有很大关系吗？

Answer 1

您的双循环的时间复杂度为 O(n)，因为迭代总数为 n。

修改 for 循环的循环变量被认为是不好的做法。我会使用 while 循环来代替。

请注意，内部循环有一个错误 - 它需要检查它是否不会继续超过缓冲区末尾。