前缀和算法的时间复杂度
前缀和算法的时间复杂度
提问于 2018-04-03 16:31:41
给定以下伪代码，我想知道在试图确定时间复杂性时，我的思维过程是否正确。
for i = 0 to n-1
Add the numbers A[0] thru A[i].
Store the result in B[i].该算法将循环n次，由于最后一次迭代将需要最多的计算量(n次计算)，该算法总共将进行n^2 + f(n)计算。其中f(n)是一次n^2 或更小的多项式，因此该算法是二次O(n^2)算法。
回答 2
Stack Overflow用户
回答已采纳
发布于 2018-04-03 16:45:32
由于Add the numbers A[0] thru A[i].的时间复杂性是\Theta(i)，所以代码的时间复杂性将是\Theta(1 + 2 + 3 + ... + \Theta(n)) = \Theta(n^2)。因此，您对代码的分析是正确的。
Stack Overflow用户
发布于 2018-04-03 16:55:03
我们可以用以下代码替换您的代码
for i 0 to n - 1
for j 0 to i
b[i] += a[j] <---为了找到这个算法的大O，我们需要计算执行第3行的次数。
为了简单起见，让我们假设所有ai元素都等于1，所以如果我们在0到n-1时找到bi的和，那么我们就可以找到运行第3行的次数。
i: b[i]
0: 1
1: 2
2: 3
..
n - 1: n因此，所有Bi的总和为n* (n + 1) /2，即O(n^2)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/49634980
复制相关文章
相似问题
腾讯云开发者
