使用求和的时间复杂度 Big Oh

Question

关于推导表达式以使用求和找到 运行时间的几个问题。 Big-Oh 时间复杂度已经给出，所以使用求和来找到复杂度是我关注的重点。

所以我知道在循环的第一次迭代之前有 2 条指令必须是 运行，还有 2 条指令必须是 运行，（比较和递增 i ) 在第一次迭代之后。当然，for 循环中只有 1 条指令。所以得出我有 2n + 3，去掉 3 和 2，我知道时间复杂度是 O(n)。

到这里我知道如何开始写求和了，但是for循环中的增量还是让我有点摸不着头脑。 这是我拥有的：

所以我知道我的求和时间复杂度推导是错误的。 关于我哪里出错的任何想法？ 谢谢

Answer 1

只需在顶部使用 n / 2，在底部使用 i = 1：

它是 i = 1 而不是 i = 0 的原因是因为 for 循环的条件是 i < n 所以你需要考虑一次，因为在求和中，i 将一直增加到 n / 2 而不是 1 短。