1

我们的教授和各种材料说 Summation(n) = (n) (n+1) /2，因此是 theta(n^2)。但直观地说，我们只需要一个循环来找到前 n 项的总和！所以，它必须是 theta(n)。我想知道我在这里错过了什么？！

4

4 回答 4

2

所有这些答案都像原来的问题一样误解了这个问题：重点不是衡量一个算法对整数求和的运行时复杂度，它是在讨论如何推理算法的复杂性，该算法i在每次通过时i采取步骤1..n. 考虑插入排序：在i插入原始列表的一个成员的每一步中，输出列表的i元素都很长，因此i执行插入需要（平均）步骤。插入排序的复杂度是多少？它是所有这些步骤的总和，或ifor iin的总和1..n。该总和是n(n+1)/2其中有一个n^2，因此插入排序是O（n ^ 2）。

于 2013-09-14T01:34:41.980 回答
2

这段代码的运行时间是Θ(1)（假设加法/减法和乘法是常数时间运算）：

result = n*(n + 1)/2 // This statement executes once

您所描述的以下伪代码的运行时间确实是Θ(n)：

result = 0
for i from 1 up to n:
    result = result + i // This statement executes exactly n times

这是另一种计算它的方法，其运行时间为Θ(n²)：

result = 0
for i from 1 up to n:
    for j from i up to n:
        result = result + 1 // This statement executes exactly n*(n + 1)/2 times

所有这三个代码块都计算从1到的自然数之和n。

此Θ(n²)循环可能是您被要求分析的类型。每当您有表单的循环时：

for i from 1 up to n:
    for j from i up to n:
        // Some statements that run in constant time

您的运行时间复杂度为Θ(n²)，因为这些语句执行准确的summation(n)时间。

于 2013-09-14T01:10:05.320 回答
1

我认为问题在于您错误地假设求和公式具有时间复杂度 theta(n^2)。

该公式中有一个 n^2，但它不需要与 n^2 成比例的计算次数或时间量。

正如您所说，将循环中的所有内容加总为 n 将是 theta(n)，因为您必须遍历循环 n 次。

但是，计算等式 n(n+1)/2 的结果将只是 theta(1)，因为它是一个执行一次的计算，无论 n 有多大。

于 2013-09-14T01:12:50.520 回答
0

Summation(n) 为 n(n+1)/2 是指从 1 到 n 的数字之和。这是一个数学公式，可以在没有 O(1) 时间的循环的情况下计算。如果您迭代一个数组以对所有值求和，这是一个 O(n) 算法。

于 2013-09-14T01:10:28.447 回答