LeetCode資料結構_BigO

 

一個數學記號，用來來評估⼀一個函式的時間複雜度或空間複雜度。

時間複雜度

同一個函式的執⾏行行時間因為 input 的不同⽽而產⽣生的變化

空間複雜度

同⼀個函式所需的空間因為 input 的不同⽽而產⽣生的變化

O(1)

void sayTruth(int x) {
    for (int i = 0; i < 10; i++) {
        std::cout << "test";
    }
}

O(N)

void sayTruth(int x) {
    for (int i = 0; i < x; i++) {
        std::cout << "test";
    }
}

O(N^2)

void sayTruth(int x) {
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < x; j++) {
            std::cout << "test";
        }
    }
}

常數或倍數不會改變複雜度相對於 input 的關係，不用考慮
(皆為已知，不會影響一個函數複雜度本質)

O(2N)

void sayTruth(int x) {
    for (int i = 0; i < x; i++) {
        std::cout << "test";
    }
    
    for (int i = 0; i < x; i++) {
        std::cout << "test";
    }
}

O(2n) 並沒有改變執⾏行行時間是線性成長的事實

計算 Big O 時不考慮倍數

因此O(2N) = O(N)

O(N+1)

void sayTruth(int x) {
    for (int i = 0; i < x + 1; i++) {
        std::cout << "test";
    }
}

O(n + 1) 並沒有改變執⾏行行時間是線性成長的事實

計算 Big O 時不考慮常數

因此O(N+1) = O(N)

若倍數或常數未知，仍需納入考量

O(X+Y)

void sayTruth(int x, int y) {
    for (int i = 0; i < x; i++) {
        std::cout << "test";
    }

    for (int j = 0; j < y; j++) {
        std::cout << "test2";
    }
}

O(X*Y)

void sayTruth(int x, int y) {
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            std::cout << "test";
        }
    }
}

Input 指數成長，複雜度線性成長O(log n)

• Input 10^0 -> 執⾏ 1 次

• Input 10^1 -> 執⾏ 2 次

• Input 10^2 -> 執⾏ 3 次

底數對Big O無影響

Binary Search(二分搜尋法)

在⼀個已經被排序過的 integer array （sorted array）中搜尋特定的 integer ，每次都把 array從中間切⼀半。當中位數等於⽬標時，即找到答案。

二分搜尋法程式碼

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include <iostream> int binarySearch(int intArray[], int target, int length) { int low = 0; int high = length - 1; while (high >= low) { int middle = (low + high) / 2; if (intArray[middle] == target) { return middle; } if (intArray[middle] < target) { low = middle + 1; } if (intArray[middle] > target) { high = middle - 1; } } return -1; } int main() { int intArray[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // 假設有排序過的整數陣列 int target = 5; // 假設目標值為 5 int length = sizeof(intArray) / sizeof(int); // 計算陣列長度 int result = binarySearch(intArray, target, length); if (result == -1) { std::cout << "目標值不存在於陣列中\n"; } else { std::cout << "目標值在陣列中的索引為: " << result << "\n"; } return 0; }

Case1.

在 {1} 中找出 1

以 1 為中位數 -> {1} -> 找到 1

執⾏ 1 次

Case2.

在 {1, 2, 6, 7, 9, 17, 18, 30, 66, 99} 中找出 2

以 9 為中位數切⼀半 -> {1, 2, 6, 7}

以 2 為中位數切⼀半 -> {1, 2} - > 找到 2 

Input 已經變為 10 倍⼤，但執⾏次數只多 1 次

Case3.

在 {1, 2, 6, 7, 9, 17, 18, 30, 66, 99} 中找出 66

以 9 為中位數切⼀半 -> {17, 18, 30, 66, 99}

以 30 為中位數切⼀半 -> {66, 99} 

以 66 為中位數切⼀半 -> {66} -> 找到 66

執⾏ 3 次