algorithm - 「ログ」は漸近表記で何を表しますか?

Question

私は漸近記法の原則を理解しており、たとえば何かが O(1) または O(n ² ) である場合にそれが何を意味するかを理解しています。しかし、O(log n) とはどういう意味ですか? または O(n log n) たとえば?

Answer 1

ログは「対数」の略です: http://en.wikipedia.org/wiki/Logarithm

対数は、たとえば、数値を表すために必要な桁数や、N 個の要素を追加したときに平衡木に含まれるレベルの数を示します。

Answer 2

チェック: en.wikipedia.org/wiki/Big_O_notation

log は指数関数よりもゆっくりと増加することに注意してください。したがって、n ^ 2 であり、同じことを行う他のアルゴリズムが対数関数を持っている場合、後者はより効率的です (一般的には、常にではありません!)。

関数 (またはアルゴリズム) の複雑さを評価するには、主に時間と空間での実行を考慮する必要があります。関数またはアルゴリズムを他のパラメーターで評価することはできますが、最初は、これら 2 つで問題ありません。

編集: http://en.wikibooks.org/wiki/Data_Structures/Asymptotic_Notation

また、並べ替えアルゴリズムを確認してください。複雑さについての優れた洞察を提供します。

Answer 3

logは数学関数です。これはべき乗の逆です-2^nの対数（基数2）はnです。実際には、正のc（1/2（平方根）などの小数cを含む）の場合はn^cよりも優れています。詳細については、ウィキペディアを確認してください。