ビッグオーの表記法

これは、アルゴリズムの実行速度を決定する表記法です。この速度は秒数ではなく、要素が増加するにつれてアルゴリズムの実行時間がどれだけ増加するかによって決まります。

ビッグオーは時間とサイズの関係です。記事全体でこれらの尺度を示すグラフが表示され、実際に使用すると理解が深まります。 2 種類の複雑さ (空間的および時間的) があります。

時間的複雑さ: 入力のサイズに比例してアルゴリズムの実行にかかる時間を決定します。

空間複雑さ: 必要な項目を見つけるために割り当てられるメモリの量を決定します。

なぜこれを勉強するのでしょうか？

• これにより、アルゴリズムがどの程度スケーラブルであるかを判断できます
• Big O は常に最悪のケースに対処します。以下の例:

例:

• リストがあり、項目を検索したいと考えていますが、その項目はリストの最後にあります。最悪のシナリオは、必要なデータが見つかるまで、できるだけ多くの操作を実行する必要があるということです。

---

実行時間

テンポコンスタンテ O(1):

• 配列のサイズに関係なく、常に同じ時間がかかります

例:

• 増加または減少

function increment(value: number){
  return ++value
}

function decrement(value: number){
  return --value
}

• 特定のアイテムを取る

const fruits = ["apple", "orange", "grape", "banana"]

function getItem(items: string[], index: number) {
  return items[index]
}

const item = getItem(fruits, 2)
console.log(`fruit: ${item}`) // "grape"

• 配列の最初の要素を取得します

const animes = ["one piece", "dragon ball", "naruto", "demon slayer"]

function getFirstElement(items: string[]){
 return items[0]
}

• 配列内の最後の項目を取得します

const animes = ["one piece", "dragon ball", "naruto", "demon slayer"]

function getLastElement(items: string[]){
 return items[item.length - 1]
}

let lastElement = getLastElement(animes)
console.log(`Last Element: ${lastElement}`)

線形時間 O(n):

• 実行時間は配列のサイズに比例して増加します
• 並べ替えおよび二分探索アルゴリズム
• ループを 1 つだけ使用した反復

例:

• 10 項目の配列で最大の数値を見つけるには、見つかるまですべての項目をスクロールします。
• 最悪の場合、最大数が最後のものになります。

const numbers = [0, 4, 8, 2, 37, 11, 7, 48]

function getMaxValue(items: number[]) {
    let max = numbers[0];
    for (let i=0; i <= items.length; i++){
      if(items[i] > max) {
        max = items[i]
      }
    }

    return max;
}

let maxValue = getMaxValue(numbers)

console.log(`Max Value: ${maxValue}`)

対数時間 O(log n)

• 入力サイズは n ずつ増加し、実行時間は log n ずつ増加します。時間は対数比例して増加します。
• n は配列内の要素の数であることに注意してください。
• 入力は実行時間よりも速く増加します。

例:

• 配列内で二分検索を実行して、特定の項目を見つけます。

const numbers = [0, 9, 24, 78, 54, 88, 92, 100, 21, 90]

function binarySearch(nums: number[], target: number) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let middle = Math.floor((right + left) / 2);

        if (nums[middle] === target) {
            return middle;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }

    return -1;
}

let getTarget = binarySearch(numbers, 92)
console.log(`Target: ${getTarget}`)

• 対数増加をよりよく理解するために、次のように見てみましょう。例で使用している配列には 10 個の入力があるため、次のようになります。

log2(10) = 3.4
log2(20) = 4.3
log2(40) = 5.3

• 以下のグラフを見ると理解しやすくなります:

線形/準線形時間 O(n log n)

• 対数演算を n 回実行することを指すアルゴリズムの時間計算量。
• O(log(n)) と O(n) の混合物。
• 構造の例は、マージソートです。
• 適度に成長します。

• 一方の部分は n でスケールし、もう一方の部分は log(n) でスケールします。以下の例は幸運なマージです。

function increment(value: number){
  return ++value
}

function decrement(value: number){
  return --value
}

二次時間 O(n²)

• 入力数が増加すると、実行時間は二次関数的に増加します。
• 読み取りマトリックス。
• 基本的に 2 つのネストされたループが必要な場合
• バブルソート

例:

const fruits = ["apple", "orange", "grape", "banana"]

function getItem(items: string[], index: number) {
  return items[index]
}

const item = getItem(fruits, 2)
console.log(`fruit: ${item}`) // "grape"

時間指数 O(2＾n)

• 各要素が入力に挿入されると、実行時間は 2 倍になります。

• このコードの例はフィボナッチです

const animes = ["one piece", "dragon ball", "naruto", "demon slayer"]

function getFirstElement(items: string[]){
 return items[0]
}

階乗時間 O(n!)

• 実行時間は入力のサイズに応じて階乗的に増加します。

例:

• 配列内のすべての順列を生成する

const animes = ["one piece", "dragon ball", "naruto", "demon slayer"]

function getLastElement(items: string[]){
 return items[item.length - 1]
}

let lastElement = getLastElement(animes)
console.log(`Last Element: ${lastElement}`)

---

以上がビッグオーの表記法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。