アルゴリズム複雑度詳細
6174 ワード
アルゴリズム複雑度詳細
この文章では、 O(1)、O(n)、O(logn)、O(nlogn)…の違いおよび分析方法 時間の複雑さの優劣比較は、まずo(1)、o(n)、o(logn)、o(nlogn)と、対応するアルゴリズムの時間複雑さを表すもので、アルゴリズムの時間複雑さの表現である.時間の複雑さを表すだけでなく、空間の複雑さを表すためにも使われます. アルゴリズムの複雑さは時間複雑さと空間複雑さに分けられる.その役割:時間の複雑さとは、このアルゴリズムを実行するために必要な計算作業量をいう. 空間複雑度とは、このアルゴリズムを実行するために必要なメモリ空間のことである. Oの後ろの括弧には、あるアルゴリズムの消費時間／消費空間とデータの増加量との関係を指定する関数があります.ここでnは入力データの量を表します.
O(1)、O(n)、O(logn)、O(nlogn)…の違いと分析方法時間の複雑さはO(n)−線形次数であり、代表的なデータ量は数倍増大し、消費時間も数倍増大する.例えば一般的なエルゴードアルゴリズム. 時間の複雑度O(n^2)—二乗では、データ量がn倍増加すると、nの二乗倍の時間がかかり、これは線形よりも高い時間複雑度である.例えば発泡秩序化は、典型的なO(n x n)のアルゴリズムであり、n個の数に対して規則化され、n x n回のスキャンが必要である. 時間の複雑度O(log n)−対数階では、データがn倍増加すると、logn倍が増大する(ここのlogは2をベースとしています.例えば、データが256倍増加すると、8倍だけ増大し、線形よりも低い時間の複雑さです.).二分検索はO(logn)のアルゴリズムであり、一度に半分を除外する可能性があります.256個のデータの中で検索すれば8回で目的を見つけることができます. countが服2になる度に、nからもっと近いです.つまり、いくつかの2乗がnより大きいと、ループが終了します.x=lognは2^x=nから得られます.このサイクルの時間複雑度はOです.時間の複雑度O(n logn)−線形対数段は、nにlognを掛け、データが256倍増大すると、256＊8＝2048倍増大する.この複雑さは線形よりも2乗以下である.並べ替えとは、O(nlogn)の時間の複雑さである. O(1)—定数次数:最低の時空複雑度、つまり、入力データの大きさに関係なく、入力データが何倍増大しても、消費時間・消費空間は変化しない.ハッシュアルゴリズムは典型的なO(1)時間の複雑さであり、データの規模がどれほど大きいかにかかわらず、一度に計算した後に目標を見つけることができる.
この文章では、
O(1)、O(n)、O(logn)、O(nlogn)…の違いと分析方法
// N
count = 0;
for(int i = 0;i < 10 ; i ++){
count ++;
}
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)
int count = 1;
while(count < n)
{
count = count*2;
// O（1）
......
}
```js
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;
}
```
index = a;
a = b;
b = index;
//