アルゴリズム分析で遭遇するほとんどの複雑さは、通常、1 つの単語で表すことができます。
O(1)== "定数"O(log n)== "対数"O(n)== "線形"O(n^2)== "二次方程式"O(n^3)== "立方体"O(2^n)== "指数"
複雑さを伴うアルゴリズムには、ある程度の規則性をもって遭遇しますO(n log n)(ソートの複雑さが支配的なアルゴリズムをすべて考えてみてください)。しかし、私の知る限り、その複雑さを表すのに英語で使える単語は 1 つもありません。これは私の知識のギャップでしょうか、それとも計算の複雑さに関する英語の議論に本当にギャップがあるのでしょうか。
ベストアンサー1
O(n log n)==「線形」
ロバート・セジウィックが著書の中で作った言葉のようだ。C のアルゴリズム準線型または対数線型とも呼ばれます。ただし、線型には、過剰な意味を持つ用語ではないという利点もあります (準線型は経済学や微分方程式で使用され、対数線型は経済学や回帰分析で使用されます)。