线性复杂度 O(20n) 能否支配多项式复杂度 O(n^2/3)？
Can linear complexity O(20n) dominate polynomial complexity O(n^2/3)?
复杂度为 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 中哪个订单是正确的。
O(n^b) ⊆ O(n^a) if b <= a
O(20*n) = O(n) = O(n^1)
O(n^(2/3)) ⊆ O(n^1)
关于polynomial time复杂性的几句话
An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is O(n^k) for some nonnegative integer k, where n is the complexity of the input.
因此，具有O(20*n)和O(n^(2/3))时间复杂度的算法都具有多项式时间复杂度。 'Linear complexity' 只是多项式的子情况。
复杂度为 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 中哪个订单是正确的。
O(n^b) ⊆ O(n^a) if b <= a
O(20*n) = O(n) = O(n^1)
O(n^(2/3)) ⊆ O(n^1)
关于polynomial time复杂性的几句话
An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is
O(n^k)for some nonnegative integerk, wherenis the complexity of the input.
因此，具有O(20*n)和O(n^(2/3))时间复杂度的算法都具有多项式时间复杂度。 'Linear complexity' 只是多项式的子情况。