漸近時間の複雑さを計算するときは、変数が他のものを支配することができますか？

Question

文字列のリストをソートする最悪の場合のシナリオの漸近時間の複雑さを表現したい場合は、長さ $ k $ 文字。 Merge Sortを使用して、 $ n $ のリストをソートするには、 $ o（n \ log n）$ 。長さの2つの文字列を比較する $ k $ のコストは、 $ o（k）$ のコストです。したがって、コストは $ O（kn \ log n）$ です。

しかし、 $ k $ 、 $ n $ の制限があります。問題。特に、 $ 0 \ lt k \ leq 20 $ 、および $ 0 \ lt n \ leq 80000 $ 。言い換えれば、リスト内の単語の数は単語の長さよりもはるかに大きい範囲で変わるかもしれません。

その場合は、 $ n $ を超える $ k $ であると言ってください。したがって、コストは $ O（n \ log n）$ として表現できますか？それとも漸近的な費用について議論しているという事実は、それらの制限が無意味なものになります（私たちが、彼らが実際に成長することができるかにかかわらず、各変数の成長によってどのように影響されるかを説明しているので）。一般に、2つの変数が独立している場合、それらのうちの1つを特定の状況下で漸近的なコストから解除することは可能ですか？

Answer 1

まず、 $ k $ と $ n $ の場合、すべての複雑さが再構築されています $ o（1）$ 。したがって、より良い仮定は、 $ k= o（\ log n）$ のようなものです。この仮定の下では、例えば、 $ o（k + n）= o（n）$ 、さえ $ O（k + \ log n）= o（\ log n）$ 。ただし、 $ o（kn）= o（n）$ 、必ずしも真実ではないので、ではできません。 $ k=log n $ の場合、 $ O（kn）= o（n）$ 。代わりに、 $ O（kn）= o（n \ log n）$

です。