big-o - O(nⁿ) と O(n!) の時間計算量

Answer 1

Answer 2

N = 4 と仮定します。

• O(N!) を呼び出すと、ループは N! を繰り返します。各ループの時間。1 番目のループは 1、2 番目のループは 1、2、3 番目のループは 1、2、3、4 番目のループは 1、2、3、4 になります。
• だからあなたは持っています：
• 1
• 1、2
• 1、2、3
• 1、2、3、4
• O(N^N) を呼び出すと、ループはループごとに N 回繰り返されます。1 番目のループは 1、2、3、4 になります 2 番目のループは 1、2、3、4 になります 3 番目のループは 1、2、3、4 になり、4 番目のループは 1、2、3、4 になります
• だからあなたは持っています：
• 1、2、3、4
• 1、2、3、4
• 1、2、3、4
• 1、2、3、4
• したがって、反復ごとにリストの最後までループする必要がないため、O(N!) は O(N^N) よりも早く終了することがわかります。したがって、時間計算量 O(N!) < O(N^N) またはむしろ O(N!) は O(N^N) より優れています。