ホームページ バックエンド開発 PHPチュートリアル PHP のカウントソートアルゴリズムの原理と時間計算量分析を学びます。

PHP のカウントソートアルゴリズムの原理と時間計算量分析を学びます。

Sep 21, 2023 pm 02:12 PM
php 分析する 原理 時間の複雑さ カウントソート

PHP のカウントソートアルゴリズムの原理と時間計算量分析を学びます。

PHP のカウント並べ替えアルゴリズムの原理と時間計算量分析を学習する

カウント並べ替えは非比較並べ替えアルゴリズムであり、小規模で既知のデータ範囲に適しています。の場合。その基本的な考え方は、各要素の出現数を数え、それを順番に出力配列に入力して並べ替えを行うことです。この記事では、カウントソートの原理、手順、時間計算量分析を紹介し、具体的な PHP コード例を示します。

  1. 原則:
    カウントソートの原則は比較的単純です。並べ替える配列が配列で、要素範囲が [0, k] であるとします。まず、各要素の出現数をカウントするために、サイズ k 1 のカウント配列 count を作成する必要があります。元の配列を反復処理している間に、要素がカウントされ、count 配列に格納されます。次に、count 配列内の要素を順次累積して、出力配列内の要素の位置を決定します。最後に、元の配列 array を走査し、各要素を対応する位置 (count のインデックスに従って) に配置して並べ替えを完了します。
  2. 手順:
  3. サイズ k 1 の count 配列 count を作成し、0 に初期化します。
  4. 元の配列 array を走査し、各要素の出現数をカウントし、それを count 配列に格納します。
  5. count 配列を累積して、出力配列内の各要素の位置を決定します。
  6. 元の配列と同じサイズの出力配列出力を作成します。
  7. 元の配列を再度スキャンし、count 配列のインデックスに従って各要素を出力配列に配置します。
  8. 出力配列の出力は、カウントソート後の結果です。
  9. 時間計算量の分析:
  10. count 配列を作成する時間計算量は O(k) です。
  11. 元の配列を走査し、各要素の出現をカウントする時間計算量は O(n) です。
  12. count 配列を累積する時間計算量は O(k) です。
  13. 出力配列作成の時間計算量は O(n) です。
  14. 元の配列を再度走査し、要素を出力配列に配置する時間計算量は O(n) です。
  15. 合計時間計算量は 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 サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

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

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

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

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

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

CakePHP プロジェクトの構成 CakePHP プロジェクトの構成 Sep 10, 2024 pm 05:25 PM

この章では、CakePHP の環境変数、一般設定、データベース設定、電子メール設定について理解します。

Ubuntu および Debian 用の PHP 8.4 インストールおよびアップグレード ガイド Ubuntu および Debian 用の PHP 8.4 インストールおよびアップグレード ガイド Dec 24, 2024 pm 04:42 PM

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

CakePHP の日付と時刻 CakePHP の日付と時刻 Sep 10, 2024 pm 05:27 PM

Cakephp4 で日付と時刻を操作するには、利用可能な FrozenTime クラスを利用します。

CakePHP ファイルのアップロード CakePHP ファイルのアップロード Sep 10, 2024 pm 05:27 PM

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

CakePHP ルーティング CakePHP ルーティング Sep 10, 2024 pm 05:25 PM

この章では、ルーティングに関連する次のトピックを学習します。

CakePHP について話し合う CakePHP について話し合う Sep 10, 2024 pm 05:28 PM

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

PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法 PHP 開発用に Visual Studio Code (VS Code) をセットアップする方法 Dec 20, 2024 am 11:31 AM

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

CakePHP バリデータの作成 CakePHP バリデータの作成 Sep 10, 2024 pm 05:26 PM

Validator は、コントローラーに次の 2 行を追加することで作成できます。

See all articles