データ構造の時間的複雑さと空間的複雑さ

データ構造の時間的複雑さと空間的複雑さ

記事ディレクトリ

前言

一、データ構造とは何ですか.

二、アルゴリズムとは何ですか.

三、アルゴリズム効率

四、時間複雑度

五、空間複雑度

六、大O漸進的表現法

文書ディレクトリ
前言
本稿では,データ構造における時間的複雑さと空間的複雑さ,および大きなOの漸進的表現について述べる.その前にデータ構造とは何かを知らなければなりませんか?アルゴリズムとは?アルゴリズムの効率性と、私たちがよりよく理解できるようにします.
一、データ構造とは何ですか.
データ構造は、コンピュータがデータを格納し、組織する方法であり、特定の方法でデータを組織する.
二、アルゴリズムとは何ですか.
良い計算プロセスを定義し、1つまたは1つの値のセットを入力とし、1つまたは1つの値のセットを生成して出力します.簡単に言えば、アルゴリズムは入力データを出力結果に変換するための一連の計算ステップです.
三、アルゴリズム効率
アルゴリズム効率は2つに分けられる:1つ目は時間効率であり、2つ目は空間効率である.時間効率を時間複雑度,空間効率を空間複雑度と呼ぶ.時間の複雑さは主にアルゴリズムの実行速度を測定し、空間の複雑さは主にアルゴリズムに必要な余分な空間を測定する.
四、時間複雑度
時間複雑度:コンピュータ科学では、アルゴリズムの時間複雑度は関数であり、このアルゴリズムの実行時間を定量的に記述する.一般に,1つのアルゴリズムにかかる時間は文で実行される回数に比例するので,時間複雑度をアルゴリズムの基本操作の実行回数と理解できる.
五、空間複雑度
空間複雑度は、実行中にアルゴリズムが一時的に格納空間のサイズを占有するメトリックです.空間複雑度はプログラムがどれだけbytesの空間を占有しているかではなく、これはあまり意味がないので、空間複雑度は一時的に余分な空間を占有する個数を計算します.
六、大きいOの漸進的な表現
一般的には大Oで複雑さを記述するが,実行回数を計算する際には,正確な実行回数を計算する必要はなく,おおよその実行回数を必要とするだけであり,これが大Oの漸進的な表現である.使用説明:1、運転時間中のすべての加算定数2を定数1で置換し、修正後の運転回数関数では、最上位次数のみを保持します.3.最上位レベルが1でない場合、その項目に乗じた係数を除去する.大きなOの漸進的表現は,結果にあまり影響を及ぼさない項目を除去し,実行回数をより簡潔に表した.
たとえば、fun()が基本的に何回コードを実行したかを計算してください.

void fun(int N)
{
     
	int count = 0;
	for (int i = 0; i < N; i++)
	{
     
		for (int j = 0; j < N; j++)
		{
     
			++count;
		}
	}
	for (int k=0; k < 2 * N; k++)
	{
     
		++count;
	}
	int M = 10;
	while (M--)
	{
     
		++count;
	}
	printf("%d
", count);
}

以上のコードからfunの基本動作回数:F(N)=N^2+2*N+10;
大きなOの漸進的表現を用いた後,funの時間的複雑度はO(N^2)であった.
いくつかのアルゴリズムでは複雑度が最も良く,平均的で,最悪の場合がある.最良の場合:任意入力規模の最小運転回数;平均状況:任意入力規模の所望運転回数;最悪:任意入力規模の最大運転回数;実際に注目されるのは最悪の運行状況です.
例えば、長さNの配列で1つのデータがXであることを検索する.最良の状況:1回見つける;最悪の場合:N回見つけた;平均:N/2回見つけた;したがって、データの中でXデータを検索する時間の複雑度はO(N)である.