lognとは何ですか?

簡単に言うと、マニアックなコンピューター サイエンス用語で、ドメイン名として気に入るほど短かったということです。 他の人が何と言おうと、これは「ログイン」のスペルミスではありません。 また、”log” の後に文字 “n” を続けて発音する傾向があります。

長いバージョンでは、それは非常に効率的なアルゴリズムのクラスを記述するために使用する用語であるということです…

Time Complexity

コンピュータ科学では、アルゴリズムはしばしば、タスクを実行するのに、時間またはメモリの量を消費して比較されます。 これらの比較を公平でわかりやすくするために、タスクのサイズとタスクを完了するために必要なステップ数の関係に基づいて分析する。

例えば、数値のリストを平均化したいとする。 これを行うには、すべての数値を合計し、その数値の数で割る必要があります。 平均化する数値の数が2倍になれば、2倍の時間がかかることになる。 これは線形複雑性の例である。項目の数 (n と略す) が増加すると、タスクを完了する時間は同じ割合で増加する。

確かに線形時間よりはるかに悪いことができる。多くのタスクは完了するのに多項式または指数的な時間さえ必要とする! 数字のリストの並べ替えが良い例で、データに対して何度もパスを行い、最終的な順序にすべてをふるいにかける必要がある。

しかしながら、線形時間よりも優れたアルゴリズムも存在する。 人間が1から100までの数字を考え、コンピュータがそれを推測するゲームを考えてみましょう。 コンピュータが間違った答えを出した場合、人間はその答えが推測より「高い」か「低い」かをコンピュータに伝えます。

すべての推測は残りの数字プールを半分に分割するので、これらの繰り返された半分が合成され、逆指数:alogarithmが作成されます。 事実上、問題を解くためのステップ数は、問題空間が指数関数的に成長するにつれて、直線的に増加します。 別の見方をすれば、問題の大きさが2倍になると、ステップ数は1つしか増えないことになります(問題の大きさが2倍になるとステップ数も2倍になる線形アルゴリズムと比較してみてください)。 この関係を logn と略記し、n(問題サイズ)が大きくなると、ステップ数はその数の対数だけであることを示す。

したがって、対数アルゴリズムは非常に効率的で、よく評価されている。

コメントを残す

メールアドレスが公開されることはありません。