线性复杂度O(20n)能否支配多项式复杂度O(n ^ 2/3)？

Question

复杂度为O(n ^ 2/3)的算法图(多项式复杂度):

复杂度为O(20n)(线性复杂度)的算法图:

不同复杂程度的优势顺序:

O(1)<O(logn)<O(n)<O(nlogn)<O(n ^ 2)<O(2 ^ n)<O(n!)

问题: 如果我所限定的两个以上的算法之间显性的顺序n^2/3和20n,我很困惑,哪一个是第一位.

根据不同复杂度的支配顺序,我看到多项式复杂度支配线性复杂度.

订单1:

O(n ^ 2/3)<O(20n)

但是从图中我们可以看出,对于O(20n)运算数量增加的元素数量的增长率大于O(n^2/3).

订单2:

O(20n)<O(n ^ 2/3)

我需要澄清一下订单1或订单2中的哪个订单是正确的.

Answer 1

O(n^b) ? O(n^a) if b <= a

O(20*n) = O(n) = O(n^1)

O(n^(2/3)) ? O(n^1)

关于多项式时间复杂度的几个词

如果完成给定输入的算法所需的步骤数是O(n^k)针对某个非负整数的k,那么算法在多项式时间内是可解的,其中n输入的复杂性.

因此,算法O(20*n)和O(n^(2/3))时间复杂度都具有多项式时间复杂度."线性复杂度"只是多项式的一个子句.