Big O Notation: それは何ですか?なぜ重要ですか?

これは楽しいですね！ Big O とのコミュニケーションは、キャリアの浅い開発者にとって、最初の顔が溶けるような移行の 1 つです。

その理由を見てみましょう。

でもまずはピットストップ。小学校で習ったまったく馬鹿げた文章問題を覚えていますか?

サリーは食料品店に行き、スイカを 37 個買いました。彼女は20ドルを持っていました。スイカ 1 個の価格は 0.70 ドルです。サリーは家に帰ったとき、お金をいくら持っていますか?

「サリーはいったいどうやって家に帰るの? スイカが 37 個もあるのに?! メロンを置くスペースのある Uber を利用するには 6.00 ドルでは足りないでしょう... サリーは何をしているの?!」と疑問に思ったことがありますか?

バカなサリー。

これは木のために森を失うことだと言う人もいます。これは練習問題を作成するための非常に怠惰な方法だと私は言います。

Big O Notationの目的は、私たちの技術の品質について他の人々と話し、文字通りコミュニケーションできるようにすることです。ここで特に焦点を当てているのは、入力サイズが増加した場合の最悪のシナリオにおけるソリューション間の比較を可能にすることです。

私たちは、潜在的な解決策 ( 「アルゴリズム」と言うのと同じこと) について抽象的に語れるようにしたいと考えています。これは重要な点です。要約すると。私たちは、自分たちが持っているデータについてはまったく気にしません。これらのアイデアを試すときは、理論的には巨大だが有限のデータセットを想定します。

私たちが持っているデータについて考えるとき、これは具体的な推論です。 Big O Notation について考えるとき、私たちは抽象的な推論をしています。具体的な推論に頼るのは簡単です。ここは私たちが人生のほとんどを過ごす場所です。それは簡単で、通常は明白で、快適です。

今、通りを渡ったほうがいいでしょうか？車はありますか？いいえ？さて、クロス。

抽象的に推論するときはやめてください。

定義を簡単に

ここで一つお願いをしてもよろしいでしょうか？邪魔になる可能性のある数学用語もたくさんあります。以下は、Big O の一般的な用語を最良のケースから最悪のケースまで順番に示した図です。用語にとらわれずに考えて学習できるように、これらが必要です。

O(1) - 「一定時間」

入力がどれほど大きくても、システムは常に同じ時間内で結果を返します。

O(log n) - 「ログ時間」

ソリューション (またはアルゴリズム) が入力に対して反復するにつれて、各反復が高速化します。

O(n) - 「線形時間」

アルゴリズムが反復されると、各反復には前の反復と同じ時間がかかります。

O(n log n) -ここでは難しい用語は使用しません

アイデアを組み合わせることができることを示しています (すごい)。反復するにつれて、各反復は遅くなりますが、遅くなるのはかなりゆっくりです。

O(n^2) - 「n の 2 乗」

反復ごとに、反復速度はかなり早く遅くなります。

O(n!) - 「n 階乗」

反復ごとに、反復速度が超高速で遅くなります。

目標は、「n 階乗」からできるだけ離れて、定数よりも大幅に悪化しないようにすることです。

以上のことを理解した上で、ギャップを埋めてみましょう。

具体的思考と抽象的思考の間のギャップを埋める

Big O 記法を理解する

Big O 表記は、アルゴリズム (ソリューション) のパフォーマンスまたは複雑さを記述するために使用されます。これにより、入力のサイズが大きくなるにつれてアルゴリズム (ソリューション) がどのように実行されるかについての高度な理解が得られます。

たとえば、複雑度が O(n) のアルゴリズムの実行時間は、入力のサイズに応じて直線的に増加します。

具体的思考と抽象的思考

この課題は、開発者が特定のデータに関する推論をアルゴリズム自体に関する推論と間違えたときに発生します。 「しかし、このデータは本物です」のようなフレーズは、この混乱を示している可能性があります。

実際のデータについて推論することは開始に役立ちますが、ソリューションを現在の入力から分離することが重要です。

なぜ誤解が生じるのでしょうか？

キャリアの浅い開発者は、大規模な問題の経験が不足していたり、現在の問題の詳細に夢中になりすぎたりするために、この間違いを犯す可能性があります。スケーラブルなソリューションを作成するには、抽象的な複雑さから具体的な詳細を分離することが不可欠です。

実際的な結果

入力が 100 倍または 100,000 倍に増加すると、アルゴリズムはどうなりますか?信じられないほど複雑なソリューションの複雑さは、データセットが大きくなると崩壊する可能性があります。

小規模なデータ セットでは問題ないと思われるアルゴリズムでも、大規模なデータ セットでは大幅に失敗し、パフォーマンスの問題やその他の課題が発生する可能性があります。

抽象的に考えることを学ぶ

問題について抽象的に考える能力を養うには、練習と指導が必要です。いくつかの戦略には次のようなものがあります。

• 抽象モデルの作成: 一般化された方法で問題を表現します。

• アルゴリズムをデータから切り離して分析する: 特定のデータポイントに関係なくアルゴリズムがどのように動作するかを評価します。

• スケーリング シナリオの構築: さまざまなサイズの入力でアルゴリズムがどのように実行されるかを想像します。

一般に抽象的思考、特に Big O Notation は、アルゴリズム設計、言い換えれば、問題の解決策を考える上で不可欠なスキルです。

問題の複雑さとアルゴリズムの複雑さを区別する方法を学ぶことで、開発者は一人で作業するときによくある落とし穴を回避し、問題解決能力を向上させることができ、また、この方法でコミュニケーションする方法を学ぶために同様に時間を費やした他の人々と協力して作業する能力を劇的に向上させることができます。

複雑な問題には、複雑な解決策が必要ない場合がほとんどです。 (サリーはおそらく最初から 37 個のスイカを必要としませんでした…37 個のスイカをどうするつもりですか?!)