performance - Big-O 表示法的计算复杂度

Question

如何根据输入大小以 Big-O 表示法指定其执行遵循以下模式的算法的计算复杂度？

Input size: 4
Number of execution steps: 4 + 3 + 2 + 1 = 10

Input size: 5
Number of execution steps: 5 + 4 + 3 + 2 + 1 = 15

Input size: 6
Number of execution steps: 6 + 5 + 4 + 3 + 2 + 1 = 21

Answer 1

从技术上讲，您没有提供足够的信息来确定复杂性。根据迄今为止的信息，对于所有大于 5 的输入大小，它可能需要 21 个步骤。在这种情况下，无论大小 4 和 5 的行为如何，它都是 O(1)。复杂性是关于限制大输入大小的行为，不是关于三个极小尺寸的东西的行为方式。

如果大小为 n 的步数通常是从 1 到 n 的数字的总和，那么步数的公式确实是 n(n+1)/2，它是 O(n^2)。

Answer 2

对于遵循模式 1 + 2 + 3 + 4 + ....+n 的任何系列，系列的总和为 n(n+1)/2，即 O(n^2)..

在您的情况下，步数永远不会是 n^2，因为在每个级别上，我们都会少走一步（n + n-1 + n-2），但是使用大哦符号来指定上界一个函数的增长率因此你的大 O 将是 O(n^2) 因为它超过 n 步数但小于 n^2 步数。

Answer 3

我认为它应该是O(N)，因为它就像：给定一个 N 大小的数组，并对其进行迭代（如果我们不关心加计算时间）。

顺便说一句，我认为这(n + 1)*n/2只是求和的结果，而不是算法的复杂性。