对或错：对于足够大的 n，O(n^3) 算法比 O(n^4) 算法快 运行
True or false: O(n^3 ) algorithm will run faster than a O(n^4 ) algorithm for sufficiently large n
我对如何提出这个问题有点困惑。
我的直觉是，在绘制 n^3 和 n^4 时，该陈述是正确的
但是，当应用常量时，例如100n^3，这个说法是错误的。
我怎么会想到这个问题？
如果他们使用非正式定义（确实是大 Theta），那么答案显然是肯定的。
如果他们使用正式定义，那么答案是否定的。原因是说一个算法是 O(f(n)) 意味着您可以为所有足够大的 n 生成 上限 形式的 c f(n) 边界。所以合并排序是 O(n^4) 算法，冒泡排序是 O(n^3)。 （不是您可以设置的最佳界限，但两个界限都有效。）但是对于大型 n，合并排序运行得更快。
我对如何提出这个问题有点困惑。 我的直觉是，在绘制 n^3 和 n^4 时，该陈述是正确的 但是，当应用常量时，例如100n^3，这个说法是错误的。 我怎么会想到这个问题？
如果他们使用非正式定义（确实是大 Theta），那么答案显然是肯定的。
如果他们使用正式定义，那么答案是否定的。原因是说一个算法是 O(f(n)) 意味着您可以为所有足够大的 n 生成 上限 形式的 c f(n) 边界。所以合并排序是 O(n^4) 算法，冒泡排序是 O(n^3)。 （不是您可以设置的最佳界限，但两个界限都有效。）但是对于大型 n，合并排序运行得更快。