3/12指導点検点
11899 ワード
時間の複雑さ
アルゴリズムを実行する時間ではなく、アルゴリズムを実行する時間です.
T(n)の形で表されるが,時間的複雑さは通常bigoで表される.
大文字(O(n))
演算回数が多項式で表される場合、最高次項を除く全ての項と最高次項の係数を表す
最悪の場合を表すのに用いられる(通常は最悪の場合を用いると仮定する)
ベストはヴィック・オメガ、普通はヴィック・セタ
const function (num) {
let sum = 0 //대입 1회
for (let i = 0; i < num; i++) { //반복문 n+1회
sum += i //덧셈 n회
}
for (let i = 0; i < num; i++) { //반복문 n+1회
sum += i //덧셈 n회
}
return sum //리턴 1회
}タグ時間の複雑さ
O(1):一定時間
const function (num) {
console.log(num)
}O(logn):ログ時間
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)
}
}
}
출처: [Plus Ultra]バイナリナビゲーションの例
O(n):線形時間
for (let i = 0; i < n; i++) {
...
} O(n²) : セカンダリタイム
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
...
}
} O(2ⁿ):指数時間
const function (num) {
if (num <= 1) {
return num
}
return function(num-2) + function(num-1)
} 1つの関数を呼び出すたびに、関数を再帰的に2回呼び出す
アルゴリズムのパフォーマンスグラフ
くうかんふくざつさ
タスクの実行時に使用するスペースの数を表示
アルゴリズムで使用するメモリ量=スペースの複雑さ
空間の複雑さに影響する4つの要因
O(n)
function sample(arr, n) {
let s = 0 // 1
for (let i = 0; i < n; i++) { // 2
s += arr[i] // n
}
return s
} O(1)
function sample(n) {
let val = 1; // 1
for(let i=0; i<n; i++) { // 2
val = val * i;
}
return val;
}Reference
この問題について(3/12指導点検点), 我々は、より多くの情報をここで見つけました https://velog.io/@qjastar/3-12-멘토링-체크포인트テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol