for(i=0;i<n;i++)
{
for(;arr[i]!=' ';i++)
{
//required code
}
//required code
}
假设我想执行一些操作,例如“反转句子中的每个单词(而不是整个句子)。例如:
输入:“这是一个球”
输出:“ sihT si llab”
'。
然后肯定在循环内,我将寻找“空格”字符。我想问以下事情:
(1)这样,我使用了两个循环,为什么有人说我不必要地通过使程序成为O(n ^ 2)来使程序变得更加复杂。
我知道我可以在外部“ for”循环内使用“ if”代替内部“ for”。但是,如果我选择这种方式,这将是O(n ^ 2),因为我认为我正在增加相同变量“ i”的循环,所以我认为它是O(n)。
(2)为什么“我写了什么”(inner for loop代替“ if”)被认为不是好习惯?它与缓存问题有很多关系吗?
最佳答案
您的双循环的时间复杂度为O(n)
,因为迭代的总数为n
。
修改for
循环的循环变量被认为是不好的做法。我会改用while
循环。
请注意,内部循环有一个错误-它需要检查它是否不会继续到缓冲区末尾。
关于c - 如果我对嵌套循环使用相同的变量,则时间复杂度为n的阶数或n的平方,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/27962151/