PHP のカウントソートアルゴリズムの原理と時間計算量分析を学びます。
PHP のカウント並べ替えアルゴリズムの原理と時間計算量分析を学習する
カウント並べ替えは非比較並べ替えアルゴリズムであり、小規模で既知のデータ範囲に適しています。の場合。その基本的な考え方は、各要素の出現数を数え、それを順番に出力配列に入力して並べ替えを行うことです。この記事では、カウントソートの原理、手順、時間計算量分析を紹介し、具体的な PHP コード例を示します。
- 原則:
カウントソートの原則は比較的単純です。並べ替える配列が配列で、要素範囲が [0, k] であるとします。まず、各要素の出現数をカウントするために、サイズ k 1 のカウント配列 count を作成する必要があります。元の配列を反復処理している間に、要素がカウントされ、count 配列に格納されます。次に、count 配列内の要素を順次累積して、出力配列内の要素の位置を決定します。最後に、元の配列 array を走査し、各要素を対応する位置 (count のインデックスに従って) に配置して並べ替えを完了します。 - 手順:
- サイズ k 1 の count 配列 count を作成し、0 に初期化します。
- 元の配列 array を走査し、各要素の出現数をカウントし、それを count 配列に格納します。
- count 配列を累積して、出力配列内の各要素の位置を決定します。
- 元の配列と同じサイズの出力配列出力を作成します。
- 元の配列を再度スキャンし、count 配列のインデックスに従って各要素を出力配列に配置します。
- 出力配列の出力は、カウントソート後の結果です。
- 時間計算量の分析:
- count 配列を作成する時間計算量は O(k) です。
- 元の配列を走査し、各要素の出現をカウントする時間計算量は O(n) です。
- count 配列を累積する時間計算量は O(k) です。
- 出力配列作成の時間計算量は O(n) です。
- 元の配列を再度走査し、要素を出力配列に配置する時間計算量は O(n) です。
- 合計時間計算量は O(k) O(n) O(k) O(n) O(n) で、O(n k) に簡略化されます。
以下は、PHP 言語を使用して計数並べ替えアルゴリズムを実装するコード例です。
function countingSort($array) { $maxValue = max($array); $count = array_fill(0, $maxValue + 1, 0); $n = count($array); foreach ($array as $value) { $count[$value]++; } for ($i = 1; $i <= $maxValue; $i++) { $count[$i] += $count[$i - 1]; } $output = array_fill(0, $n, 0); for ($i = $n - 1; $i >= 0; $i--) { $output[$count[$array[$i]] - 1] = $array[$i]; $count[$array[$i]]--; } return $output; } $array = [4, 2, 0, 1, 3, 2, 1]; // 待排序数组 $sortedArray = countingSort($array); print_r($sortedArray);
上記は、計数の原理と時間計算量分析を学習する内容です。 PHPのソートアルゴリズム。これがカウントの並べ替えを理解するのに役立つことを願っています。
以上がPHP のカウントソートアルゴリズムの原理と時間計算量分析を学びます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ホットAIツール

Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

AI Hentai Generator
AIヘンタイを無料で生成します。

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

SublimeText3 中国語版
中国語版、とても使いやすい

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

SublimeText3 Mac版
神レベルのコード編集ソフト(SublimeText3)

ホットトピック











PHP 8.4 では、いくつかの新機能、セキュリティの改善、パフォーマンスの改善が行われ、かなりの量の機能の非推奨と削除が行われています。 このガイドでは、Ubuntu、Debian、またはその派生版に PHP 8.4 をインストールする方法、または PHP 8.4 にアップグレードする方法について説明します。

ファイルのアップロードを行うには、フォーム ヘルパーを使用します。ここではファイルアップロードの例を示します。

CakePHP は、PHP 用のオープンソース フレームワークです。これは、アプリケーションの開発、展開、保守をより簡単にすることを目的としています。 CakePHP は、強力かつ理解しやすい MVC のようなアーキテクチャに基づいています。モデル、ビュー、コントローラー

Visual Studio Code (VS Code とも呼ばれる) は、すべての主要なオペレーティング システムで利用できる無料のソース コード エディター (統合開発環境 (IDE)) です。 多くのプログラミング言語の拡張機能の大規模なコレクションを備えた VS Code は、
