algorithm - 功能增长中的大O

Question

假设我们有两个算法，A 和 B，用于解决一些问题(比如将两个 n × n 矩阵相乘，或者对一个矩阵进行排序整数数组 n)。令 n 表示问题的输入大小，令 T_A(n) 和 T_B(n) 表示步数分别由算法 A 和 B 在大小为 n 的输入上采用。已知 T_A(n) = O(n³) 和 T_B( n) = O(n⁵)。对于足够大的 n，算法 A 执行的步骤少于算法 B 是真的吗？为什么或为什么不？

Answer 1

首先，我想你的意思是边界是O(n³) 和O(n⁵)(即分别为 3 和 5 的幂)。

自 O is an upper bound ，你真的不能说什么比较。例如:

• n² = O(n³)，并且 n^1.5 = O(n⁵)，但是，即使对于大的n，前一个函数也比后者大。

• 相反，n^1.5 = O(n³)，并且n² = O(n⁵)，这里，对于大的n，前者的函数确实比后者大。

如果问题是关于Θ，而不是O，答案就会不同——在那种情况下，你可以说，对于足够大的 n，前者比后者执行更少的步骤。