我最近参加了一次编程面试,出现了以下代码。面试官告诉我这是一个 O(n*n) 算法,但我很困惑这是怎么回事,考虑到每次外循环运行时内循环运行的次数更少。
绝对不是 O(n),但为什么是 O(n*n)?
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
...
}
}
最佳答案
这样看。第一次通过 i
时,您将循环 j
99 次。接下来,98、97、96 等,一直到 1。这等于:
1 + 2 + 3 + 4 + 5 + ... + n
对这些 ( triangular) 数字求和的快速方法是使用 attributed to Gauss 技术:
sum = ((n * n) + n) / 2
现在您可以清楚地看到 O(n*n)。
关于algorithm - 递减嵌套for循环的运行时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19102684/