确定这个例子的 big-o

Question

所以前几天我在考试中遇到了这道题，但我答错了，但我不知道我的 'new' 答案是否真的正确。我所有的同学也不能直接给我一个答案，所以我才在这里问你们。

所以问题基本上是 "Out of different tests, the next table has been made up, what would the big-O of the alghorithm be?"。在此示例中，table 的左侧是元素的数量，右侧是处理所需的时间。

所以我的新答案实际上是 O(n)，因为经过两倍数量的元素所需的时间大约翻了一番。但在这里我想知道这真的是正确的吗？我应该在我的大 O 符号中更具体吗？忽略时间上的微小差异是否可以，而且时间不完全是原来的两倍？

Answer 1

正如你说的那样"O(n), because the time it takes to go through twice the amount of elements aproximately is doubled"因为O(n)中的"n"是一个函数，并不表示时间上正好是1比1的关系，是O(n)如果速度呈线性，并且如果时间按时间元素为 (n * 1/2 + 1) 或 (n * 2) 或 (n + 1) 则可能是线性的。所以你现在的回答是正确的。

Answer 2

对于 O(n)，它不必完全线性缩放。结果图大致呈线性这一事实强烈表明我们确实在处理 O(n) 的复杂性。

查看 the plot of the data，线性特性非常明显！

Answer 3

如果您实际划分连续项，数据看起来像 n 翻倍时，相应的运行时间增加了一个徘徊在 2.2 左右的因子。如果这不仅仅是意外，而是表明运行时的真实渐近行为，那么它确实几乎线性，但不完全是。即函数可能更像这样：

T(n) = 10 * 2.2 ^ (log_2(n/5000))

Table 个值：

n      T(n)
5000   10
10000  22
20000  48
40000  106
80000  234
160000 515

在那种情况下，一些快速代数表明

T(n) = 10 * 2.2 ^ (log_2(n/5000))
     = 10 * 2 ^ (log_2(2.2)log_2(n/5000))
     = 10 * (n/5000)^log_2(2.2)
     ~ 10 * (n/5000)^1.1375

也许这是一个更好的答案，也许更糟。不可能说出任何有限样本的渐近行为是什么，但这个答案 - O(n^log(2.2)) - 可能会更充分地利用所有可用数据。

Answer 4

我不太确定，但我会将其计算为 O (n ^ 0.26)

确定这个例子的 big-o

Determening the big-o of this example

big-o

computer-science