runtime - 运行时分析大 O

Question

我想知道运行时分析是否适用于 O(n^2) 是否也适用于 O(n^3)，反之亦然？我得到了一个问题 O (n^3) 的运行时，有人得到了 O (n^2)。但她说可能两者兼而有之

标签： runtimebig-o

Answer 1

如果其他人与您处理相同的问题并确定运行时间为O(n^2)，那么根据定义O(n^3)，也必然会遇到相同的问题。如果其他人是正确的，您的问题是O(n^3)您报告的界限不是可以给出的最严格的界限。实际上，它离最严格的界限还很远。

一般来说，最严格的界限是我们想要报告的算法或运行时间，因为这告诉我们解决问题可能需要多少计算能力。因此，您应该查看您的答案并尝试查看您是否也能获得O(n^2)约束。