アルゴリズムは、問題を解決したり作業を完了したりするために、あらかじめ決められた順序で実行される一連の命令です。関数は、プログラムの他の部分から呼び出して実行できるコードのブロックです。
問題を解決したり、特定のアクティビティを実行したりするための一連の指示。コンピューター サイエンスでは、アルゴリズムは基本的な数学から複雑なデータ処理まで、幅広い操作に使用されます。
C で使用される一般的なアルゴリズムの 1 つはソート アルゴリズムです。並べ替えアルゴリズムは、項目のコレクションを数値順またはアルファベット順などの特定の順序に並べます。
並べ替えアルゴリズムは多数あり、それぞれに長所と短所があります。 C での最も一般的な並べ替えアルゴリズムは、クイックソート、マージ、ソートです。
C の重要な機能の 1 つはポインターのサポートです。これにより、配列、キューなどのデータ構造を効率的に操作できるようになります。これにより、並べ替えやアルゴリズム検索など、複雑なデータ操作を必要とするアルゴリズムの実装に適しています。
C で実装されたソフトウェア ライブラリの有名な例の 1 つは、標準テンプレート ライブラリ (STL) です。このライブラリは、データ構造の並べ替え、検索、操作などのタスク用のさまざまなアルゴリズムを提供します。
アルゴリズムの特徴
これは、次のようなアルゴリズムのいくつかの重要な機能を定義します。
アルゴリズム解析
アルゴリズム分析は、効率、複雑さ、その他の基準の観点からアルゴリズムのパフォーマンスを評価するプロセスです。通常、これは多くのアルゴリズムを評価し、特定の問題またはソフトウェアに対する最適なソリューションを選択するために行われます。
アルゴリズムの分析には、通常、その時間と空間の複雑さを測定することが含まれます。
必要なメモリまたはディスク容量の量を表す空間計算量と同様に、時間計算量はアルゴリズムがタスクの実行にかかる時間を決定する時間を表します。
Big O や Omega 表記など、アルゴリズムの時間計算量を分析するにはさまざまな方法があります。オメガ シンボルはアルゴリズムの時間計算量の上限を提供し、オメガ シンボルは下限を提供します。
アルゴリズム分析には、時間と空間の複雑さの測定に加えて、安定性、並列性、スケーラビリティなどの他の基準も含まれます。
これには 2 種類の分析が含まれます。
彼らです：-
Javaでの有効な識別子
- 事前分析。
- 事後分析。
事前分析
Prior は、アルゴリズムを実際に実行せずに、数学的特性に基づいてアルゴリズムのパフォーマンスを推定することに重点を置いたアルゴリズム分析方法です。
このアプローチにより、アルゴリズムを実装して実行することなく、アルゴリズムの時間と空間の複雑さおよびその他のメトリクスを分析できます。
事後分析
一方、事後分析は、実際にアルゴリズムを実行してそのパフォーマンスを測定するアルゴリズム分析手法です。
このアプローチでは、アルゴリズムのパフォーマンスに関するより正確かつ詳細な情報が提供されますが、アルゴリズムの実装と実行が必要です。
アルゴリズムの複雑さ
アルゴリズムの複雑さは、アルゴリズムの効率とパフォーマンスを測定する尺度です。アルゴリズムは通常、問題を解決したり特定の目標を達成したりするために必要な時間とスペースの観点から評価されます。
アルゴリズムの複雑さには 2 つの要素が使用されます。
彼らです：-
- 時間要因。
- スペース係数。
時間要因
- アルゴリズムがタスクを実行するために必要な時間は、時間計算量と呼ばれます。通常、問題を解決するためにアルゴリズムが実行する必要がある操作またはステップの数によって測定されます。
- アルゴリズムの時間計算量は、実行にかかる時間を決定し、プログラムやシステムのパフォーマンスに大きな影響を与える可能性があるため、重要です。
- アルゴリズムの時間計算量は、アルゴリズムの時間計算量の上限を表現する方法である Big O 表記法を使用して表現できます。
- 時間計算量が O(n) のアルゴリズムは、アルゴリズムの実行に必要な時間が入力データのサイズ (n) に正比例することを意味します。
- その他の一般的な時間計算量には、O(n^2) 二次計算量と O(log n) 対数計算量があります。
空間分析
- 一方、スペースの複雑さは、アルゴリズムの実行に必要なメモリまたはストレージスペースの量を指します。
- これは、アプリケーションまたはシステムの全体的なパフォーマンスに影響を与える可能性のあるアルゴリズムの実行に必要なリソースの数を決定するため、重要です。
- アルゴリズムの空間複雑さが O(n) の場合、使用するメモリ量は入力のサイズに比例して増加します。
- アルゴリズムの空間複雑度が O(1) の場合、入力のサイズに関係なく、固定量のメモリが使用されます。
アルゴリズムの書き方
1. まず、アルゴリズムで解決したい問題を定義します。
たとえば、数値のリストから最大値を見つけるアルゴリズムを作成したいとします。
2. 問題を、管理しやすい小さなステップに分割します。
- 「max」変数をリストの最初の値に初期化します。
- リスト内の後続の各値について、「max」と比較します。
- 値が「max」より大きい場合は、「max」をその値に設定します。
- リスト内のすべての値が比較されるまで、これを続けます。
- 最終的な「最大」値を返します。
3. アルゴリズムを疑似コードまたはプログラミング言語で作成します。
擬似コードで書かれたアルゴリズム:
MAX (list) max = list[0] For i = 1 the length of the list list IF[i] > max max = list[i] End for Maximum return Maximum end
4. アルゴリズムをテストして、正しく効率的であることを確認します。
さまざまな数値リストを入力し、最大の正しい値が返されることを確認することで、アルゴリズムをテストできます。アルゴリズムの時間計算量を分析して、より大きな入力に対してアルゴリズムがどの程度適切にスケーリングできるかを判断することもできます。
例：-
入力: [1、5、2、7、3]
出力: 7。
説明: 7 はリストの最大値です。
Javaのスタックとは何ですか
5. アルゴリズムを最適化します。
アルゴリズムを最適化し、より高速かつ効率的にする方法を探してください。これには、疑似コードの変更や、より効率的なデータ構造やアルゴリズムの実装が含まれる場合があります。
アルゴリズムの基本的な書き方
例: - 2 つの整数の合計。
ステップ1 - 始めましょう
ステップ2 - 3 つの整数 a、b、c を宣言します。
ステップ3 - a と b の値を定義します
ステップ4 - a と b の値を加算します
ステップ5 - ステップ 4 の出力を c に保存します。
ステップ6 - プリントc
ステップ7 - 停止
C言語で使用されるアルゴリズムの種類。
1. ソートアルゴリズム
C には、バブル ソート、挿入ソート、クイック ソートなどのさまざまなソート アルゴリズムの実装に使用できるデータ型と演算子の豊富なセットが用意されています。
これらのアルゴリズムは、さまざまなサイズやタイプのデータを並べ替えるのに使用できるため、多くのアプリケーションで役立ちます。
さまざまな並べ替えアルゴリズムがあります。
彼らです：-
(i) バブルソート: 近くのコンポーネントを繰り返し比較し、順序が崩れている場合はそれらを切り替える単純な並べ替えアルゴリズム。
バブルソートのアルゴリズムは次のとおりです:-
- ソートされていない要素のリストから始めます。
- リスト内の最初の 2 つの要素を比較します。最初の要素が 2 番目の要素より大きい場合は、それらを交換します。
- 次の要素のペアに進み、リストの最後に到達するまで手順 2 を繰り返します。
- リストの各項目について、手順 2 と 3 をもう一度繰り返します。それはパスと呼ばれます。
- リスト全体に対して手順 2 ～ 4 を繰り返します。パスを繰り返すと、要素がソートされたリスト内の正しい位置に「バブルアップ」します。
- パスが完了し、スワップが行われなくなると、リストがソートされ、アルゴリズムが停止します。
- 最終的にソートされたリストが返されます。
(ii) 挿入ソート : それぞれの要素を適切な場所に配置することによって、一度に 1 つずつ個別の要素を並べ替えたリストを作成する並べ替え方法。
挿入ソートのアルゴリズムは次のとおりです。
- ソート対象の要素の空のソート済みリストとソートされていないリストを初期化します。
- 未ソートのリストから最初のメンバーを取得し、ソート済みリストの適切な位置に配置する必要があります。
- 未ソートのリストの後続の要素ごとに手順 2 を繰り返します。
- 現在の要素を、すぐ左側の要素から始めて、並べ替えられたリスト内の要素と比較します。
- 現在の要素がその左側の要素より小さい場合は、2 つの要素を交換します。
- 現在の要素がその左側の要素より大きい場合は、ソートされたリスト内の正しい位置にその要素を挿入します。
- 並べ替えられていないリストの後続の要素ごとに手順 4 ～ 6 を繰り返します。
- すべての要素が処理されると、ソートされたリストにはすべての要素が正しい順序で含まれます。
- 並べ替え処理が完了しました。
(iii) 選択ソート : 順序なしのリストから最も詳細な情報を含む並べ替えられたリストを一貫して開始する並べ替え方法。
選択ソートのアルゴリズムは次のとおりです:-
- まず、リストの主要素を min 要素として設定します。
- リスト内の残りの項目を繰り返し、各項目を現在の最小値と比較します。
- 要素が既存の要素よりも小さいことが判明した場合は、新しい最小値を設定します。
- 結論に達するたびに、現在の最小値をリストの最初の要素に変更します。
- リストの残りの未ソート部分については、手順 2 ～ 4 を繰り返しますが、リストの 2 番目の項目から始めます (最初の要素はすでにソートされているため)。
- すべての並べ替えが完了するまで、この方法でリストの並べ替えを続けます。
(iv) クイックソート : ピボット要素を選択し、要素がピボットよりも少ないか多いかに応じてリストをサブリストに分割する分割統治型並べ替えアルゴリズム。その後、完全なリストがソートされるまで、サブリストが繰り返しソートされます。
クイックソートのアルゴリズムは次のとおりです:-
- リストからピボット要素を選択します。これは通常、最初の要素ですが、ランダムな要素またはリストの中央値にすることもできます。
- リストを 2 つのサブリストに分割します。1 つはピボットよりも小さい要素を含み、もう 1 つはピボットよりも大きい要素を含みます。
- 同じプロセスを使用して、ピボットよりも小さい要素を含むサブリストを再帰的に並べ替えます。
- 同じ手順を使用して、ピボットより大きいエントリのサブリストを再帰的に並べ替えます。
- ソートされたサブリストを間にピボット要素を挟んで連結して、完全にソートされたリストを形成します。
- 完全にソートされたリストを返します。
(v) ロットは当たります : 分割統治ソート アルゴリズムは、リストを 2 つの半分に分割し、それぞれをソートしてから、ソートされた順序で 2 つの半分をマージします。
マージソートアルゴリズム:
- リストから 2 つのサブリストを作成します。1 つはピボットの下の要素を含み、もう 1 つはピボットの上の要素を含みます。
- サブリストが 1 つだけ存在するまでサブリストを繰り返しマージすることで、新しい並べ替えられたサブリストを作成します。これがソートされたリストになります。
- 2 つのサブディレクトリをマージする手順:-
- 並べ替えられた要素を保持する空のリストを作成します。
- 各サブリストの最初の要素を比較します。
- 小さい要素を新しいリストに追加し、親サブリストから削除します。
- リストが完全に空になるまで、手順 2 と 3 を繰り返します。
- 他のサブリストの残りの要素を新しいリストに追加します。
- マージされたサブリストを新しいソートされたリストに置き換えます。
- すべてのサブリストが 1 つの並べ替えられたリストにマージされるまで、このプロセスを繰り返します。
(vi) ヒープソート : ヒープと呼ばれるデータ構造を使用して要素を並べ替える並べ替えアルゴリズム。
これは分類アルゴリズムです。
- 残りの要素を積み重ねます。ルートから開始して、各ノードがその子と比較され、最大ヒープ プロパティが満たされるまでノードを古い子と交換します。
- 正しい位置にある最後の要素を除き、新しく積み重ねられた要素で手順 2 と 3 を繰り返します。
- スタックに要素が 1 つだけ残るまで、このプロセスを繰り返します。これで整理が完了しました。
(vii) 基数ソート : バイナリ表現の数字に基づいて要素を並べ替える並べ替えアルゴリズム。
基数ソートのアルゴリズムは次のとおりです。
- 入力リストの最大の要素に含まれる桁数を決定します。
- 変数、たとえば桁の桁を、現在の桁の桁を表す 1 に初期化します。
- 0 ～ 9 の可能な数字ごとに空のリストを作成します。
- 入力リストを反復処理し、現在の桁の値に基づいて各要素を適切なリストに追加します。
- すべてのリストを連結して、数字リストの順序で新しいリストを形成します。
- 次の桁に移動するには、digitPlace に 10 を掛けます。
- 最大の要素のすべての桁が考慮されるまで、桁ごとに手順 4 ～ 6 を繰り返します。
- 最終的なリストは、要素の桁の昇順に並べ替えられます。
- 最終的にソートされたリストを返します。
2. 検索アルゴリズム
C は、線形検索や二分探索などのさまざまな検索アルゴリズムを実装するために必要なツールも提供します。これらのアルゴリズムは、データ セット内の特定の項目を迅速に見つけることができるため、幅広いアプリケーションに役立ちます。
検索アルゴリズムにはさまざまな種類があります。
彼らです：-
(i) 線形探索 : 目的のアイテムが見つかるまで、リスト内の各アイテムを 1 つずつ調べる基本的な検索アルゴリズム。
線形探索のアルゴリズム:-
- アルゴリズムの入力を定義します。線形探索アルゴリズムの入力は、要素 (または配列) のリストと検索対象のターゲット要素です。
- 「index」という変数を -1 に初期化します。この変数は、ターゲット要素が見つかった場合、そのインデックスを格納するために使用されます。
- 要素のリストをループする: 最初の要素から始めて、リスト内の各要素を 1 つずつチェックします。
- 現在の要素を評価のために目的の要素と比較します。現在の要素のインデックスをインデックス変数に保持し、最新の要素と目標要素が同一の場合はループを終了します。
- ターゲット要素のインデックスを返す: ループが完了したら、インデックス変数に格納されている値を返します。対象の要素が見つからない場合、インデックスの値は -1 になります。
(ii) 二分探索 : リストを半分に分割し、その半分内を検索する検索アルゴリズムでは、その要素が含まれる可能性が高くなります。
二分探索のアルゴリズム:-
- 入力: n 個の要素とターゲット要素 x のソートされたリスト。
- 変数の初期化: 低インデックスを 0、高インデックスを n-1、中間インデックスを (低+高)/2 に設定します。
- ループを開始します。下位インデックスが上位インデックス以下である間、次の手順を繰り返します。
- Mid 要素を x と比較します。mid 要素が x と等しい場合は、mid インデックスを返します。
- 低インデックスまたは高インデックスを更新します。x が中間要素より大きい場合、低インデックスを Mid + 1 に設定します。それ以外の場合、高インデックスを Mid - 1 に設定します。
- 中間インデックスを更新します: Mid = (低+高)/2。
- ループの終了: 低インデックスが高インデックスより大きい場合、x はリストに含まれず、アルゴリズムは失敗を返します。
- 出力: リストまたは失敗メッセージ内の x のインデックス。
(iii) 深さ優先探索 : 方向転換する前に、各分岐を可能な限り検査する検索アルゴリズム。
次のガイドラインは深さ優先検索に適用されます。
- 開始するグラフの開始頂点またはノードを選択します。
- 最初の頂点に訪問マークを追加します。
- 開始頂点をスタックに直接配置します。
- スタックが空になるまで、次のアクションを繰り返します。 -
- スタックの一番上の頂点を削除します。
- 訪問済みとしてマークし、ポップされた頂点の未訪問の各隣接点をスタックに挿入します。
- グラフ内のすべての頂点が訪問されるまで、このプロセスを続けます。
- すべての頂点を訪問すると、アルゴリズムが完了し、グラフに対して深さ優先検索が実行されます。
(iv) 幅優先検索 : 次のレベルに移動する前に、ノードの近隣ノードをすべて探索する検索アルゴリズム。
幅優先検索のアルゴリズムは次のとおりです。
- ルートノードまたは初期状態から開始します。
- ルート ノードをキューに追加します。
- キューが空かどうかを確認します。 「はい」の場合、アルゴリズムを終了します。
- キューから最初の要素を取得し、訪問済みとしてマークします。
- すべての未訪問の隣接ノードをキューに追加することで、現代のノードを増幅します。
- 目的のノードが見つかるか、キューが空になるまで、手順 3 ～ 5 を繰り返します。
- ゴールノードが見つかった場合は、予備状態からターゲット状態へのパスを返します。
- キューが空の場合は、一連のルールを終了し、目標状態が識別されなかったことを報告します。
(v) 補間検索 : 検索された要素の値を使用してインデックス内の位置を推定する検索アルゴリズム。
配列が均等に分散されていることが重要です。それ以外の場合はアルゴリズムです。
期待どおりに機能します。
アルゴリズムは次のように要約できます。
- 検索する入力リストとキー値を取得します。
- リストの最初と最後のインデックスで下位変数と上位変数を初期化します。
- 下限値が上限値以下の場合、次のようになります。
- 次の式を使用して推定位置を計算します。
pos = 低値 + ((高値 - 低値) / (arr[高値] - arr[低値])) * (x - arr[低値])。 - 推定位置値がキー値の場合は位置を返します。
- c) 推定位置値がキー値より小さい場合は、それを低く設定します。
位置+1。 - d) 推定位置の値がキー設定値より大きい場合、位置 - 1 上になります。
- 次の式を使用して推定位置を計算します。
- キー値が見つからない場合は、値がリストにないことを示す -1 を返します。
(vi) ジャンプ検索 : 関連する要素が見つかるか、その要素が存在しないと判断されるまで、一定長のステップでリストを反復する検索メソッド。
ジャンプ検索アルゴリズムは次のとおりです。
- まず、ジャンプ サイズを配列要素数の平方根に設定します。
- 「current」という名前の変数を配列の最初の要素に設定します。
- 「jump」と呼ばれる変数をインクリメントしながら、ジャンプ サイズごとにジャンプすることで配列を反復処理します。
- 既存の要素が目的の要素より小さい場合は、次のステップに進みます。
- 現在の要素がターゲット要素より大きい場合は、現在の要素と前のジャンプ要素の間で線形探索を実行して、ターゲット要素を見つけます。
- ターゲット要素が配列内に見つからない場合は、配列内にないことを示す -1 を返します。
- 要素が見つかった場合は、配列内の要素のインデックスを返します。
3. グラフアルゴリズム
C はポインタと、配列やリンク リストなどのデータ構造をサポートしているため、グラフ内の 2 つのノード間の最短パスを見つけるなど、グラフを操作するアルゴリズムの実装に適しています。
グラフアルゴリズムにはさまざまな種類があります。
彼らです：-
4. 暗号アルゴリズム
C は低レベルの操作と効率的なデータ操作をサポートしているため、データ暗号化アルゴリズムや復号化アルゴリズムなど、暗号化で使用されるアルゴリズムの実装に最適です。
暗号化アルゴリズムにはさまざまな種類があります。
Javaのif else文のコーディング
彼らです：-
アルゴリズムの利点
アルゴリズムには多くの利点があります。
彼らです：-
アルゴリズムの欠点
アルゴリズムはプログラミングに非常に役立ちますが、アルゴリズムには欠点もあります。
彼らです：-