アルゴリズムの複雑さ

こんにちは！今日の講義は他の講義とは少し異なります。Java に間接的にのみ関連するという点で異なります。 ただし、このトピックはすべてのプログラマーにとって非常に重要です。アルゴリズムについて話します。アルゴリズムとは何ですか? 簡単に言うと、これは、望ましい結果を達成するために実行する必要がある一連のアクションです。私たちは日常生活でアルゴリズムをよく使用します。たとえば、あなたは毎朝、学校や職場に来て、同時に次のことを行うという課題に直面しています。

• 服を着た
• クリーン
• ちゃんと育てられている

どのようなアルゴリズムを使用すればこの結果を達成できるでしょうか?

1. 目覚まし時計で起きます。
2. シャワーを浴びて、顔を洗います。
3. 朝食の準備をし、コーヒー/紅茶を作ります。
4. 食べる。
5. 夕方以降アイロンをかけていなかった場合は、アイロンをかけましょう。
6. 服を着てください。
7. 家を出ます。

この一連のアクションにより、確実に望ましい結果を得ることができます。プログラミングにおける私たちの仕事の要点は、常に問題を解決することです。これらのタスクの大部分は、既知のアルゴリズムを使用して実行できます。たとえば、配列内の 100 人の名前のリストを並べ替えるというタスクに直面しているとします。このタスクは非常に単純ですが、さまざまな方法で解決できます。解決策の 1 つは次のとおりです。 名前をアルファベット順に並べ替えるアルゴリズム:

1. インターネットで「ロシア人名辞典」1966 年版を購入またはダウンロードします。
2. この辞書のリストにあるすべての名前を見つけてください。
3. その名前が辞書の何ページに載っているかを紙に書きます。
4. メモを使って名前を紙に並べます。

このような一連の行動で問題は解決できるのでしょうか？はい、完全に許可されます。この解決策は効果があるでしょうか? しそうにない。ここで、アルゴリズムのもう 1 つの非常に重要な特性、つまり効率性について説明します。この問題はさまざまな方法で解決できます。しかし、プログラミングでも日常生活でも、私たちは最も効果的な方法を選択します。バターを使ったサンドイッチを作るのが仕事なら、もちろん、小麦を蒔いて牛の乳を搾ることから始めることができます。しかし、これは非効率な解決策であり、多くの時間と多額の費用がかかります。単純な問題を解決するには、パンとバターを買うだけです。また、小麦と牛のアルゴリズムは、問題を解決することはできますが、実際に適用するには複雑すぎます。プログラミングにおけるアルゴリズムの複雑さを評価するために、Big-O (「ビッグ O」)と呼ばれる特別な表記法が作成されました。 Big-O を使用すると、アルゴリズムの実行時間が、アルゴリズムに渡されるデータにどの程度依存するかを推定できます。最も単純な例であるデータ転送を見てみましょう。ある情報をファイルの形式で長距離 (たとえば、5000 キロメートル) に送信する必要があると想像してください。どのアルゴリズムが最も効率的でしょうか? それは彼が扱わなければならないデータによって異なります。たとえば、サイズが 10 メガバイトの音声ファイルがあるとします。 この場合、最も効率的なアルゴリズムは、インターネット経由でファイルを転送することです。ほんの数分しかかかりません。そこで、私たちのアルゴリズムをもう一度声に出してみましょう。 「5000 キロメートルの距離にわたって情報をファイル形式で転送する必要がある場合は、インターネットを介したデータ送信を使用する必要があります。」 素晴らしい。それでは分析してみましょう。 それは私たちの問題を解決しますか？一般的には、はい、完全に解決します。しかし、その複雑さについては何と言えるでしょうか? うーん、ここからが面白いことになります。実際のところ、私たちのアルゴリズムは受信データ、つまりファイルのサイズに大きく依存しています。現在 10 メガバイトがあり、すべて問題ありません。500メガバイトを転送する必要がある場合はどうすればよいでしょうか? 20ギガバイト？500テラバイト？30ペタバイト？私たちのアルゴリズムは機能しなくなりますか? いいえ、これらの量のデータはすべて転送できます。 完了までにさらに時間がかかりますか? はい、そうなります！これで、アルゴリズムの重要な特徴がわかりました。転送されるデータのサイズが大きくなるほど、アルゴリズムの完了にかかる時間が長くなります。しかし、この関係 (データのサイズと転送にかかる時間の間) がどのようなものであるかをより正確に理解したいと考えています。私たちの場合、アルゴリズムの複雑さは線形になります。。「線形」とは、データ量が増加すると、その送信時間がほぼ比例して増加することを意味します。データが 2 倍ある場合、転送には 2 倍の時間がかかります。データが 10 倍あれば、転送時間も 10 倍になります。Big-O 表記を使用すると、アルゴリズムの複雑さはO(N)として定義されます。この表記法は、将来の参照のために覚えておくと最適です。線形複雑さを持つアルゴリズムには常に使用されます。注意してください: ここでは、インターネットの速度やコンピューターの能力など、さまざまな「変動する」事柄についてはまったく話していません。アルゴリズムの複雑さを評価する場合、これは単純に意味がありません。いずれにせよ、私たちはそれを制御することができません。Big-O は、アルゴリズムが動作する「環境」に関係なく、アルゴリズム自体を評価します。 例を続けてみましょう。最終的に、転送されるファイルのサイズが 800 テラバイトであることが判明したとします。もちろんインターネットを通じて送信すれば問題は解決します。問題が 1 つだけあります。それは、私たちのほとんどが家庭で使用している標準的な最新のリンク (100 メガビット/秒) での送信には、約 708 日かかるということです。 ほぼ2年ぶり！:O したがって、私たちのアルゴリズムは明らかにここでは適切ではありません。他の解決策が必要です! 突然、IT 巨人アマゾンが私たちを助けてくれました。Amazon Snowmobile サービスを使用すると、大量のデータをモバイル ストレージ ユニットにロードし、トラックで目的の住所に配送できます。 新しいアルゴリズムが登場しました。 「情報をファイル形式で 5,000 キロメートル離れた場所に転送する必要があり、インターネット経由で転送するとそのプロセスに 14 日以上かかる場合は、Amazon のトラック輸送を使用する必要があります。」 ここで 14 日という数字はランダムに選択されました。これが許容できる最大期間であるとしましょう。アルゴリズムを分析してみましょう。速度についてはどうでしょうか？たとえ時速 50 km でトラックが走行したとしても、わずか 100 時間で 5,000 キロメートルを走行することになります。たったの4日ですよ！これは、インターネット送信オプションよりもはるかに優れています。このアルゴリズムの複雑さについてはどうですか? それも直線的になりますか、O(N)？いいえ、それはしません。結局のところ、トラックはどれだけ荷物を積むかには関係なく、ほぼ同じ速度で走行し、時間通りに到着します。800 テラバイトのデータがあっても、10 倍のデータがあっても、トラックは 5 日で到着します。言い換えれば、トラックを介してデータを配送するためのアルゴリズムは常に複雑です。「一定」とは、アルゴリズムに渡されるデータに依存しないことを意味します。1GBのフラッシュドライブをトラックに積めば、5日以内に到着します。そこに 800 テラバイトのデータが入ったディスクを置くと、5 日以内に到着します。Big-O を使用する場合、一定の複雑さはO(1)として表されます。O(N)と知り合ってから、O(1)、ここでさらに「プログラマ」の例を見てみましょう :) 100 個の数値の配列が与えられ、タスクはそれらのそれぞれをコンソールに出力することだとします。forこのタスクを実行する 通常のループを作成します。

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

書かれたアルゴリズムの複雑さはどれくらいですか? 線形、O(N)。 プログラムが実行する必要があるアクションの数は、プログラムに渡された数値の正確な数によって異なります。配列に数値が 100 個ある場合は、アクション (画面上の出力) が 100 回あり、配列に数値が 10,000 個ある場合は、10,000 回のアクションを実行する必要があります。アルゴリズムを改善できるでしょうか? いいえ。いずれの場合も、アレイを N 回パスし、コンソールへの N 回の出力を実行する必要があります。別の例を見てみましょう。

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

空のものがありLinkedList、そこにいくつかの数字を挿入します。この例に単一の数値を挿入するためのアルゴリズムの複雑さLinkedListと、それがリスト内の要素の数にどのように依存するかを見積もる必要があります。答えはO(1) - 一定の複雑さです。なぜ？注: 毎回、リストの先頭に数字が挿入されます。さらに、覚えているとおり、LinkedList要素に数値を挿入するとき、数値はどこにも移動されません。リンクは再定義されます (LinkedList の仕組みを突然忘れてしまった場合は、古い講義を見てください)。リストの最初の数値が数値である場合х、リストの先頭に数値 y を挿入すると、必要なのは次のとおりです。

x.previous  = y;
y.previous = null;
y.next = x;

この参照の再定義では、現在存在する数値の数は問題ではありませんLinkedList。少なくとも 1 つ、少なくとも 10 億です。アルゴリズムの複雑さは一定 - O(1) になります。

対数複雑度

慌てないで！:) 「対数」という言葉を聞いて、これ以上読まずに講義を閉じたいと思った場合は、数分待ってください。ここでは数学的な困難はありません (そのような説明は他の場所にたくさんあります)。すべての例を「すぐに」分析します。あなたのタスクは、100 個の数値の配列の中から特定の 1 つの数値を見つけることであると想像してください。より正確には、それが存在するかどうかを確認してください。必要な番号が見つかったらすぐに検索を停止し、「必要な番号が見つかりました!」というエントリがコンソールに表示されるはずです。配列内のインデックス = ....」このような問題をどうやって解決しますか? ここでの解決策は明らかです。最初 (または最後) から始めて配列要素を 1 つずつ繰り返し、現在の数値が目的の数値と一致するかどうかを確認する必要があります。したがって、アクションの数は配列内の要素の数に直接依存します。100 個の数値がある場合、次の要素に 100 回移動し、数値が一致するかどうかを 100 回チェックする必要があります。数値が 1000 個ある場合、チェック ステップも 1000 回あり、これは明らかに線形複雑さO(N)です。ここで、この例に 1 つの説明を追加します。数値を検索する必要がある配列は昇順でソートされます。これによって私たちのタスクに何か変化はありますか? 希望の番号を総当たりで検索することもできます。しかし、代わりによく知られた二分探索アルゴリズムを使用することもできます。 画像の一番上の行には、ソートされた配列が表示されます。その中で数値 23 を見つける必要があります。数値を反復処理する代わりに、単純に配列を 2 つの部分に分割し、配列内の平均数値をチェックします。セル 4 にある数字を見つけて確認します (図の 2 行目)。この数は 16 名で、23 名を募集しています。現在の数はさらに少なくなります。これはどういう意味ですか？以前のすべての数値 (16 番までの数値) をチェックする必要はありません。配列はソートされているため、それらは間違いなく探している数値よりも小さくなります。残りの 5 つの要素の間で検索を続けてみましょう。 注意してください：チェックは 1 つしか行っていませんが、考えられるオプションの半分はすでに除外されています。残っている要素は 5 つだけです。手順を繰り返します。再び残りの配列を 2 で除算し、再び中央の要素を取得します (図の 3 行目)。この数は 56 で、探している数よりも大きくなります。これはどういう意味ですか？さらに 3 つのオプション、つまり数値 56 自体とその後の 2 つの数値 (配列はソートされているため、これらは確実に 23 より大きくなります) を破棄します。チェックすべき数値は 2 つだけ残っています (図の最後の行)、配列インデックス 5 と 6 の数値です。最初の数値をチェックします。これが探していたもの、つまり数値 23 です。そのインデックス = 5! アルゴリズムの結果を見て、その複雑さを理解しましょう。(ところで、これでバイナリと呼ばれる理由がわかりました。その本質はデータを常に 2 で割ることです)。結果は素晴らしいものでした！線形探索を使用して目的の数値を探す場合、10 回のチェックが必要ですが、二分探索では 3 回で完了しました。最悪の場合、最後のステップで必要な数が最初ではなく 2 番目であることが判明した場合、それらは 4 つになるでしょう。その複雑さについてはどうでしょうか? これは非常に興味深い点です :) 二分探索アルゴリズムは、線形探索アルゴリズム (つまり、単純な列挙) よりも配列内の要素の数にあまり依存しません。配列内の要素が10 個 の場合、線形検索では最大 10 個のチェックが必要となり、二分検索では最大 4 個のチェックが必要になります。その差は2.5倍です。しかし、要素が 1000 個ある配列の場合、線形検索では 1000 回のチェックが必要ですが、二分検索では10 回だけ必要になります。その差はすでに100倍！ 注意してください：配列内の要素の数は 100 倍 (10 から 1000) 増加しましたが、二分探索に必要なチェックの数は 4 から 10 と 2.5 倍に増加しただけです。要素が10,000 に達すると、その差はさらに顕著になります: 10,000線形検索のチェックは 1 回、バイナリのチェックは合計 14 回行われます。また、要素の数は 1000 倍 (10 から 10000) 増加しましたが、チェックの数は 3.5 倍 (4 から 14) しか増加しませんでした。 二分探索アルゴリズムの複雑さは対数、つまり Big-O 表記ではO(log n) です。なぜそう呼ばれるのでしょうか？対数はべき乗の逆数です。バイナリ対数は、2 の累乗を計算するために使用されます。たとえば、バイナリ検索を使用して調べる必要がある要素が 10,000 個あります。 今、目の前に写真があり、これには最大 14 個のチェックが必要であることがわかります。しかし、目の前に画像がなく、必要なチェックの正確な数を数える必要がある場合はどうなるでしょうか? 単純な質問に答えるだけで十分です。「得られる結果がチェックされる要素の数以上になるように、数値 2 を何乗する必要がありますか?」 10000の場合は14乗になります。2 の 13 乗は小さすぎます (8192) しかし、2 の 14 乗 = 16384 であるため、この数値は条件を満たします (配列内の要素の数以上です)。対数 - 14 が見つかりました。必要なチェックの数はこれだけです。:) アルゴリズムとその複雑さは、1 回の講義に含めるにはあまりにも膨大なトピックです。しかし、それを知っておくことは非常に重要です。多くの面接では、アルゴリズムの問​​題を受けることになります。理論については、いくつかの本をお勧めします。まずは「 Grocking Algorithms 」から始めるとよいでしょう。この本の例は Python で書かれていますが、この本の言語と例は非常に単純です。初心者に最適なオプションであり、容量も小さいです。より本格的な読書:ロバート・ラフォレとロバート・セジウィックの本。どちらも Java で書かれているため、学習が少し簡単になります。結局のところ、あなたはこの言語にかなり精通しています。:) 優れた数学的背景を持つ学生にとって、最良の選択肢はトーマス コーマンの本でしょう。しかし、理論だけでは満足できません。 「知っている」 != 「できる」HackerRankとLeetcode でアルゴリズムの問​​題を解く練習ができます。そこからの問題は、Google や Facebook の面接でも頻繁に使用されるため、間違いなく退屈することはありません :) 講義内容を強化するために、 YouTube でBig-O に関する優れたビデオを視聴することをお勧めします。次回の講義でお会いしましょう！:)