時間複雑度(big-o)
14025 ワード
時間の複雑さとは?
アルゴリズムの処理にどれくらいの時間がかかるか教えてください
big oとは何ですか?
Big−O(Big−O)はアルゴリズムの性能を表す数学的シンボルである.これはアルゴリズムの時間と空間の複雑さを表す.大文字記号は、処理アルゴリズムの実際の時間を表しません.Bigoシンボルは、データまたはユーザ成長率に基づいてアルゴリズムの性能を予測するために使用される.
参考サイト
https://overcome-the-limits.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84-with-JavaScript
o(1):定数時間(不変時間)
アルゴリズムの処理にどれくらいの時間がかかるか教えてください
big oとは何ですか?
Big−O(Big−O)はアルゴリズムの性能を表す数学的シンボルである.これはアルゴリズムの時間と空間の複雑さを表す.大文字記号は、処理アルゴリズムの実際の時間を表しません.Bigoシンボルは、データまたはユーザ成長率に基づいてアルゴリズムの性能を予測するために使用される.
参考サイト
https://overcome-the-limits.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84-with-JavaScript
o(1):定数時間(不変時間)
入力データの大きさにかかわらず,一定時間を要するアルゴリズムをo(1)と呼ぶ.
example .1const example = [1,2,3,4,5]; function findO1(example) {
console.log(example[0]); // O(1) console.log(example[1]); // O(1)
}
findO1(example);
上のコードはelementにちょうど必要な値が印刷されているので、一度だけ実現すればいいです.
このアルゴリズムはo(1)の時間的複雑さを有する.
o(n):線形時間(増加時間)
o(n)は、データサイズに応じて処理時間を比例的に増加させるアルゴリズムを表す.const people = ['epitone', 'junggyun', 'sangsu', 'soonhee', 'hansik'];
const findPerson = array => {
for (let i = 0; i < array.length; i++) {
if (array[i] === 'hansik') {
console.log("Found hansik");
}
}
};
findPerson(people);
上のコードのように、人の列の長さが長いほど、繰り返し文の回数が比例して増えるので、そのようなアルゴリズムをo(n)と呼ぶ.
o(n^2) :Quadratic time
処理時間と入力データサイズの二乗を表すアルゴリズム
(データが大きいほど、時間は2乗で増加します)const people = ["epitone", "junggyun", "sangsu", "soonhee", "hansik"];
const findPerson = (array) => {
for (let i = 0; i < array.length; i++) {
for (let k = 0; k < array.length; k++) {
console.log(array[i], array[k]);
}
}
};
findPerson(people);
以上のように、2重扉は、人の麻縄が多ければ多いほど、時間が平方に増えます.
o(2^n)フィボナッチ数列
フィボナッチ数列を下図で示す
1,1,2,3,5,8,13,21,34
前の値と自分の値を加算し、次の値を返します.
次のコードで実現できます.function a(n){
if(n <= 0) {
return 0;
} else if(n === 1) {
return 1;
} return a(n-1) + a(n-2);
}
再帰関数によりフィボナッチ数列を求めるコードを実現すれば,このように表すことができる.
つまり、関数を呼び出すたびに、前の数値と前の数値をすぐに認識して、数値を追加しながら将来の数値を決定する必要があります.関数を呼び出すたびに2回呼び出されます.この重複木の高さ.
nの平方と比較すると、データの増加に伴ってスループットが著しく向上するグラフィックが表示されます.
o(log n)
バイナリサーチなどのアルゴリズムに使用
ソート配列で特定の数値を検索するときにバイナリ検索を使用する場合、
1.配列の中間値とキー値を比較します.
2.中間値がキー値より小さい場合、小さい値はxをナビゲートする必要がある
3.配列内のキー値より小さい値を削除する
4.1番に移動
let arr = [];
function log(k, s, e){
for(let i = s; i <= e; i++){
arr.push(i); let m = (s+e)/2;
if(arr[m] === k){
console.log(m)
} else if(arr[m]> k){
return log(k, s, m-1);
} else{
return log(k, m+1,e)
}
}
}
출처: https://overcome-the-limits.tistory.com/entry/자료구조-시간복잡도-with-JavaScript [Plus Ultra]
処理するたびに、検索するデータ量が半分に減少します.
o(logn)と呼ぶ.
図表で表す
big o表現
一緒に使用するアルゴリズムの時間的複雑さが必要です.
最も時間のかかる複雑さを無条件に示す
また,大量のデータがあるという仮定の下で表現する.
Reference
この問題について(時間複雑度(big-o)), 我々は、より多くの情報をここで見つけました
https://velog.io/@jmyoon8/시간복잡도big-o
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
const example = [1,2,3,4,5]; function findO1(example) {
console.log(example[0]); // O(1) console.log(example[1]); // O(1)
}
findO1(example);
o(n)は、データサイズに応じて処理時間を比例的に増加させるアルゴリズムを表す.
const people = ['epitone', 'junggyun', 'sangsu', 'soonhee', 'hansik'];
const findPerson = array => {
for (let i = 0; i < array.length; i++) {
if (array[i] === 'hansik') {
console.log("Found hansik");
}
}
};
findPerson(people);
上のコードのように、人の列の長さが長いほど、繰り返し文の回数が比例して増えるので、そのようなアルゴリズムをo(n)と呼ぶ.o(n^2) :Quadratic time
処理時間と入力データサイズの二乗を表すアルゴリズム
(データが大きいほど、時間は2乗で増加します)const people = ["epitone", "junggyun", "sangsu", "soonhee", "hansik"];
const findPerson = (array) => {
for (let i = 0; i < array.length; i++) {
for (let k = 0; k < array.length; k++) {
console.log(array[i], array[k]);
}
}
};
findPerson(people);
以上のように、2重扉は、人の麻縄が多ければ多いほど、時間が平方に増えます.
o(2^n)フィボナッチ数列
フィボナッチ数列を下図で示す
1,1,2,3,5,8,13,21,34
前の値と自分の値を加算し、次の値を返します.
次のコードで実現できます.function a(n){
if(n <= 0) {
return 0;
} else if(n === 1) {
return 1;
} return a(n-1) + a(n-2);
}
再帰関数によりフィボナッチ数列を求めるコードを実現すれば,このように表すことができる.
つまり、関数を呼び出すたびに、前の数値と前の数値をすぐに認識して、数値を追加しながら将来の数値を決定する必要があります.関数を呼び出すたびに2回呼び出されます.この重複木の高さ.
nの平方と比較すると、データの増加に伴ってスループットが著しく向上するグラフィックが表示されます.
o(log n)
バイナリサーチなどのアルゴリズムに使用
ソート配列で特定の数値を検索するときにバイナリ検索を使用する場合、
1.配列の中間値とキー値を比較します.
2.中間値がキー値より小さい場合、小さい値はxをナビゲートする必要がある
3.配列内のキー値より小さい値を削除する
4.1番に移動
let arr = [];
function log(k, s, e){
for(let i = s; i <= e; i++){
arr.push(i); let m = (s+e)/2;
if(arr[m] === k){
console.log(m)
} else if(arr[m]> k){
return log(k, s, m-1);
} else{
return log(k, m+1,e)
}
}
}
출처: https://overcome-the-limits.tistory.com/entry/자료구조-시간복잡도-with-JavaScript [Plus Ultra]
処理するたびに、検索するデータ量が半分に減少します.
o(logn)と呼ぶ.
図表で表す
big o表現
一緒に使用するアルゴリズムの時間的複雑さが必要です.
最も時間のかかる複雑さを無条件に示す
また,大量のデータがあるという仮定の下で表現する.
Reference
この問題について(時間複雑度(big-o)), 我々は、より多くの情報をここで見つけました
https://velog.io/@jmyoon8/시간복잡도big-o
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
const people = ["epitone", "junggyun", "sangsu", "soonhee", "hansik"];
const findPerson = (array) => {
for (let i = 0; i < array.length; i++) {
for (let k = 0; k < array.length; k++) {
console.log(array[i], array[k]);
}
}
};
findPerson(people);
フィボナッチ数列を下図で示す
1,1,2,3,5,8,13,21,34
前の値と自分の値を加算し、次の値を返します.
次のコードで実現できます.
function a(n){
if(n <= 0) {
return 0;
} else if(n === 1) {
return 1;
} return a(n-1) + a(n-2);
}
再帰関数によりフィボナッチ数列を求めるコードを実現すれば,このように表すことができる.つまり、関数を呼び出すたびに、前の数値と前の数値をすぐに認識して、数値を追加しながら将来の数値を決定する必要があります.関数を呼び出すたびに2回呼び出されます.この重複木の高さ.
nの平方と比較すると、データの増加に伴ってスループットが著しく向上するグラフィックが表示されます.
o(log n)
バイナリサーチなどのアルゴリズムに使用
ソート配列で特定の数値を検索するときにバイナリ検索を使用する場合、
1.配列の中間値とキー値を比較します.
2.中間値がキー値より小さい場合、小さい値はxをナビゲートする必要がある
3.配列内のキー値より小さい値を削除する
4.1番に移動
let arr = [];
function log(k, s, e){
for(let i = s; i <= e; i++){
arr.push(i); let m = (s+e)/2;
if(arr[m] === k){
console.log(m)
} else if(arr[m]> k){
return log(k, s, m-1);
} else{
return log(k, m+1,e)
}
}
}
출처: https://overcome-the-limits.tistory.com/entry/자료구조-시간복잡도-with-JavaScript [Plus Ultra]
処理するたびに、検索するデータ量が半分に減少します.
o(logn)と呼ぶ.
図表で表す
big o表現
一緒に使用するアルゴリズムの時間的複雑さが必要です.
最も時間のかかる複雑さを無条件に示す
また,大量のデータがあるという仮定の下で表現する.
Reference
この問題について(時間複雑度(big-o)), 我々は、より多くの情報をここで見つけました
https://velog.io/@jmyoon8/시간복잡도big-o
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
let arr = [];
function log(k, s, e){
for(let i = s; i <= e; i++){
arr.push(i); let m = (s+e)/2;
if(arr[m] === k){
console.log(m)
} else if(arr[m]> k){
return log(k, s, m-1);
} else{
return log(k, m+1,e)
}
}
}
출처: https://overcome-the-limits.tistory.com/entry/자료구조-시간복잡도-with-JavaScript [Plus Ultra]
一緒に使用するアルゴリズムの時間的複雑さが必要です.
最も時間のかかる複雑さを無条件に示す
また,大量のデータがあるという仮定の下で表現する.
Reference
この問題について(時間複雑度(big-o)), 我々は、より多くの情報をここで見つけました https://velog.io/@jmyoon8/시간복잡도big-oテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol