time-complexity - 成長関数の順序付け

Question

次の成長関数を、最も効率的なものから最も複雑なものへの順序でリストします。

1. nlog ² (n)+n ²
2. n ² -nlog(n)
3. nlog(n)
4. n ² log(n)
5. 2 ⁿ +100 n ⁴
6. n ³ -100n ²

関数が n の圧倒的な関数によって最も効率的または最も複雑であると見なされることを理解しています。しかし、ログの参照が複数ある場合の進め方がわかりません。

(5) は指数関数的な n を持ち、指数関数的に増加するため、最も複雑です。(6) は多項式であるため、複雑さが遅れます。

今私の混乱が来ます。^{n 2}の値がログ関数に追加されるため、(1) は 6 の前に来ると思います。次に (2) log 関数として減算します。次に (4) を掛けます。これにより、二重対数で最も効率的なのは 3 になります。

3
4
2
1
6
5

これはほぼ正しいですか、それとも左翼手ですか?

Answer 1

すべての に対してlog(n) ^a ∈ O(n) であることを思い出してaください。これを使用して、指定されたすべての関数を多項式/指数カテゴリに入れることができます。

1. n ² + n•log ² (n) ∈ O(n ² )
2. n ² − n•log(n) ∈ O(n ² )
3. n•log(n) ∈ O(n•log(n)) ∈ O(n ² )
4. n ² •log(n) ∈ O(n ² •log(n)) ∈ O(n ³ )
5. 100n ⁴ + 2 ⁿ ∈ O(2 ⁿ )
6. n ³ − 100n ² ∈ O(n ³ )

これで、{1,2,3} < {4,6} < 5 であることがわかりました。

{1,2,3}の内部n•log(n)は であるため、最小です< n^2。明らかにn^2 - x<n^2 + yであるため、2 は 1 より小さいです。

{4,6}の内部n^2•log(n) = n•n•log(n) < n•n•(n-100) = n^3-100n^2では、log(n) < n-100大きな n のためです。

したがって、正しい順序は 3 < 2 < 1 < 4 < 6 < 5 です。