O,O,O,Oの違いを詳しく解説

私は、アルゴリズムの研究で多くの仲間の開発者は、ソートはしばしばO（1）、O（n）、O（logn）、O（nlogn）これらの複雑さに遭遇すると信じて、ここで疑問があるでしょう参照してください、最終的にこのO（N）は、それは何を表していますか？好奇心を持って、今日の記事を開始します。

まずo(1)、o(n)、o(logn)、o(nlogn)は、対応するアルゴリズムの時間複雑度を表現するために使用されます。これは時間の複雑さを表すだけでなく、空間の複雑さを表すのにも使われます。

アルゴリズムの複雑さは、時間の複雑さと空間の複雑さに分けられます。その役割

• 時間の複雑さとは、このアルゴリズムを実行するのに必要な計算量のことです；

• 空間の複雑さは、このアルゴリズムを実行するために必要なメモリ空間です；

時間と空間の両方がコンピュータのリソースの重要な表現であり、アルゴリズムの複雑さは、そのアルゴリズムを実行するためにコンピュータがどれだけのリソースを必要とするかに反映されます；

Oの後の括弧は、特定のアルゴリズムの時間/空間消費量とデータ増加量の関係を指定する関数を含んでいます。ここでnは入力データ量を表します。

• O(n)-線形オーダーの時間複雑度は、データ量が数倍になり、消費時間も数倍になることを意味します。例として、一般的な探索アルゴリズムが挙げられます。

//結果はループをN回繰り返すことで得られる。
count = 0;
for(int i = 0;i < 10 ; i ++){
	count ++;
}

• 時間複雑度O(n^2)2乗オーダーとは、データ量がn倍になると、かかる時間もn乗倍になることを意味し、線形よりも時間複雑度が高くなります。例えば、バブリングソートは典型的なO(n x n)アルゴリズムであり、n個の数値をソートするためにn x n回のスキャンを必要とします。

 for(int i =1;i<arr.length;i++) { //n回繰り返す
 for(int j=0;j<arr.length-i;j++) {//n-1回繰り返す
 if(arr[j]>arr[j+1]) {
 int temp = arr[j];
 arr[j]=arr[j+1];
 arr[j+1]=temp;
 }
 } 
}
//全体の複雑さ n*(n-1)

• 時間の複雑さO（logn）-対数順序、データがnの要因によって増加すると、時間がlognの要因によって増加。二分ルックアップは、O（logn）アルゴリズム、可能性の半分の除去を見つけるために、各時間は、ターゲットを見つけるために8回を見つけるように長いルックアップで256のデータです。

int binarySearch(int a[], int key) {
 int low = 0;
 int high = a.length - 1;
 while (low <= high) {
 int mid = low + (high - low) / 2;
 if (a[mid] > key)
 high = mid - 1;
 else if (a[mid] < key)
 low = mid + 1;
 else
 return mid;
 }
 return -1;
}

• 時間の複雑さ O(nlogn)- nにlognを掛けた線形対数次数で、データが256倍になると、かかる時間は256*8=2048倍になります。この複雑さは2乗以下の線形よりも高いです。サブサンプションソートは O(nlogn) の複雑さです。

public void mergeSort(int[] arr, int p, int q){
 if(p >= q) {
		return
	};
 int mid = (p+q)/2;
 mergeSort(arr, p, mid);
 mergeSort(arr, mid+1,q);
 merge(arr, p, mid, q);
}
private void merge(int[] arr, int p, int mid, int q){
 int[] temp = new int[arr.length]; //ここで配列はグローバル変数として設定されている。
 int i = p, j = mid+1，iter = p;
 while(i <= mid && j <= q){
 if(arr[i] <= arr[j]) {
			temp[iter++] = arr[i++] 
		} else{
			temp[iter++] = arr[j++];
		} 
 }
 
 while(i <= mid) {
		temp[iter++] = arr[i++];
	}
	
 while(j <= q){
 		temp[iter++] = arr[j++];
	}
	
 for(int t = p; t <= q; t++) {
		arr[t] = temp[t];
	}
}

• O(1)一定次数：最も低い時間空間複雑度、つまり時間消費は入力データのサイズに依存せず、入力データが何倍になっても時間消費/空間消費は変わりません。 ハッシュアルゴリズムは一般的にO(1)の時間複雑度であり、データのサイズに関係なく1回の計算でターゲットを見つけることができます。

index = a;
a = b;
b = index;
//一度実行して結果を得る

• 時間の複雑さの長所と短所の比較 一般的な桁の大きさ：小さいほど、実行時間の頻度が短ければアルゴリズムが優れていることを示します；

O(1)< />< />< />< />< />< />< />< />< /> < />