各種時間複雜度 c++ 範例

各種時間複雜度 c++ 範例

Comments 0 Comment

各種時間複雜度 c++ 範例

資料來源: https://chatgpt.com/s/t_68ef0f807e1081919ce4c96ab4cf31b2


O(1) – 常數時間(yeah)-不論輸入大小，執行時間固定。[數學又比演算法重要的重要演示] 

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    cout << arr[2]; // 直接存取固定位置
    return 0;
}


O(log n) – 對數時間(nice)-通常出現在「每次把問題縮小一半」的演算法（例如二分搜尋）。 

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

int main() {
    vector<int> v = {1, 3, 5, 7, 9, 11, 13};
    cout << binarySearch(v, 9);
}


O(n log n) – 線性對數時間(k-ish)-常見於快速排序（QuickSort）、合併排序（MergeSort）等分治演算法。 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 9, 1, 5, 6};
    sort(v.begin(), v.end()); // C++ sort() 是 O(n log n)
    for (int x : v) cout << x << " ";
}


O(n) – 線性時間(ok)-隨著輸入資料量增加，執行時間等比例增加。[數學又比演算法重要的重要演示] 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5};
    int sum = 0;
    for (int x : v)
        sum += x; // 每個元素都要處理一次
    cout << sum;
}


O(n²) – 平方時間(my)-每個元素都要和其他元素比較，例如氣泡排序。 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {5, 3, 8, 4, 2};
    for (int i = 0; i < v.size(); ++i)
        for (int j = i + 1; j < v.size(); ++j)
            if (v[i] > v[j]) swap(v[i], v[j]);
    for (int x : v) cout << x << " ";
}


O(n³) – 立方時間-每個元素都要和其他元素比較，例如氣泡排序。 

#include <iostream>
using namespace std;

int main() {
    int n = 3;
    int sum = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            for (int k = 0; k < n; ++k)
                sum += i + j + k;
    cout << sum;
}


O(2ⁿ) – 指數時間-典型例子是遞迴解費波那契數列（無記憶化）。 

#include <iostream>
using namespace std;

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    cout << fib(20); // 計算成本隨 n 成指數增長
}


O(n!) – 階乘時間-排列組合類問題，例如產生所有排列（backtracking）。 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    do {
        for (int x : v) cout << x << " ";
        cout << endl;
    } while (next_permutation(v.begin(), v.end()));
}

上面所有整合的完整Code

// time_complexity_demo.cpp
// 各種常見時間複雜度範例 + 執行時間比較
#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
using namespace std;
using namespace chrono;

// ===== O(1) =====
void O1_example() {
    int arr[] = {1, 2, 3, 4, 5};
    volatile int x = arr[2]; // volatile 防止編譯器優化
}

// ===== O(log n) =====
int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
void OlogN_example(int n) {
    vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = i;
    binarySearch(v, n - 1);
}

// ===== O(n) =====
void ON_example(int n) {
    vector<int> v(n);
    long long sum = 0;
    for (int i = 0; i < n; ++i) sum += i;
}

// ===== O(n log n) =====
void OnlogN_example(int n) {
    vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = rand();
    sort(v.begin(), v.end());
}

// ===== O(n^2) =====
void On2_example(int n) {
    long long cnt = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cnt += i + j;
}

// ===== O(n^3) =====
void On3_example(int n) {
    long long cnt = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            for (int k = 0; k < n; ++k)
                cnt += i + j + k;
}

// ===== O(2^n) =====
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
void O2n_example(int n) {
    fib(n);
}

// ===== O(n!) =====
void permute(vector<int>& v, int l, int r) {
    if (l == r) return;
    for (int i = l; i <= r; ++i) {
        swap(v[l], v[i]);
        permute(v, l + 1, r);
        swap(v[l], v[i]);
    }
}
void OnFactorial_example(int n) {
    vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = i + 1;
    permute(v, 0, n - 1);
}

// ===== 通用時間測量工具 =====
template <typename Func>
void measure(const string& name, Func f) {
    auto start = high_resolution_clock::now();
    f();
    auto end = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(end - start).count();
    cout << name << " 耗時: " << duration << " ms" << endl;
}

// ===== 主程式 =====
int main() {
    cout << "==== 各種時間複雜度測試 ====" << endl;

    measure("O(1)", []() { O1_example(); });
    measure("O(log n)", []() { OlogN_example(1'000'000); });
    measure("O(n)", []() { ON_example(1'000'000); });
    measure("O(n log n)", []() { OnlogN_example(200'000); });
    measure("O(n^2)", []() { On2_example(1'000); });
    measure("O(n^3)", []() { On3_example(200); });
    measure("O(2^n)", []() { O2n_example(25); }); // 小心，太大會爆炸！
    measure("O(n!)", []() { OnFactorial_example(9); }); // 9! = 362,880 組合

    cout << "=============================" << endl;
    cout << "完成！可觀察不同複雜度耗時差異。" << endl;
    return 0;
}


⚙️ 附加：各複雜度增長對比（理論）

複雜度 n=10 n=20 n=50 n=100
O(1) 1 1 1 1
O(log n) 3 4 6 7
O(n) 10 20 50 100
O(n log n) 30 80 282 664
O(n²) 100 400 2500 10000
O(2ⁿ) 1024 1,048,576 — —
O(n!) 3,628,800 巨大 — —

=========================================
上面自適應HTML表格(奇偶數被景色特意強化) code

<br />
<h2 data-start="2697" data-end="2722">
	⚙️ <strong data-start="2703" data-end="2722">附加：各複雜度增長對比（理論）</strong>
</h2>
<div class="_tableContainer_1rjym_1">
	<div tabindex="-1" class="group _tableWrapper_1rjym_13 flex w-fit flex-col-reverse">
		<table data-start="2724" data-end="3034" class="w-fit min-w-(--thread-content-width)">
			<thead data-start="2724" data-end="2760">
				<tr data-start="2724" data-end="2760">
					<th data-start="2724" data-end="2730" data-col-size="sm">
						複雜度
					</th>
					<th data-start="2730" data-end="2737" data-col-size="sm">
						n=10
					</th>
					<th data-start="2737" data-end="2744" data-col-size="sm">
						n=20
					</th>
					<th data-start="2744" data-end="2751" data-col-size="sm">
						n=50
					</th>
					<th data-start="2751" data-end="2760" data-col-size="sm">
						n=100
					</th>
				</tr>
			</thead>
			<tbody data-start="2805" data-end="3034">
				<tr data-start="2805" data-end="2829">
					<td data-start="2805" data-end="2812" data-col-size="sm">
						O(1)
					</td>
					<td data-col-size="sm" data-start="2812" data-end="2816">
						1
					</td>
					<td data-col-size="sm" data-start="2816" data-end="2820">
						1
					</td>
					<td data-col-size="sm" data-start="2820" data-end="2824">
						1
					</td>
					<td data-col-size="sm" data-start="2824" data-end="2829">
						1
					</td>
				</tr>
				<tr data-start="2830" data-end="2858">
					<td data-start="2830" data-end="2841" data-col-size="sm">
						O(log n)
					</td>
					<td data-col-size="sm" data-start="2841" data-end="2845">
						3
					</td>
					<td data-col-size="sm" data-start="2845" data-end="2849">
						4
					</td>
					<td data-col-size="sm" data-start="2849" data-end="2853">
						6
					</td>
					<td data-col-size="sm" data-start="2853" data-end="2858">
						7
					</td>
				</tr>
				<tr data-start="2859" data-end="2888">
					<td data-start="2859" data-end="2866" data-col-size="sm">
						O(n)
					</td>
					<td data-col-size="sm" data-start="2866" data-end="2871">
						10
					</td>
					<td data-col-size="sm" data-start="2871" data-end="2876">
						20
					</td>
					<td data-col-size="sm" data-start="2876" data-end="2881">
						50
					</td>
					<td data-col-size="sm" data-start="2881" data-end="2888">
						100
					</td>
				</tr>
				<tr data-start="2889" data-end="2925">
					<td data-start="2889" data-end="2902" data-col-size="sm">
						O(n log n)
					</td>
					<td data-col-size="sm" data-start="2902" data-end="2907">
						30
					</td>
					<td data-col-size="sm" data-start="2907" data-end="2912">
						80
					</td>
					<td data-col-size="sm" data-start="2912" data-end="2918">
						282
					</td>
					<td data-col-size="sm" data-start="2918" data-end="2925">
						664
					</td>
				</tr>
				<tr data-start="2926" data-end="2962">
					<td data-start="2926" data-end="2934" data-col-size="sm">
						O(n²)
					</td>
					<td data-col-size="sm" data-start="2934" data-end="2940">
						100
					</td>
					<td data-col-size="sm" data-start="2940" data-end="2946">
						400
					</td>
					<td data-col-size="sm" data-start="2946" data-end="2953">
						2500
					</td>
					<td data-col-size="sm" data-start="2953" data-end="2962">
						10000
					</td>
				</tr>
				<tr data-start="2963" data-end="2999">
					<td data-start="2963" data-end="2971" data-col-size="sm">
						O(2ⁿ)
					</td>
					<td data-col-size="sm" data-start="2971" data-end="2978">
						1024
					</td>
					<td data-col-size="sm" data-start="2978" data-end="2990">
						1,048,576
					</td>
					<td data-col-size="sm" data-start="2990" data-end="2994">
						—
					</td>
					<td data-col-size="sm" data-start="2994" data-end="2999">
						—
					</td>
				</tr>
				<tr data-start="3000" data-end="3034">
					<td data-start="3000" data-end="3008" data-col-size="sm">
						O(n!)
					</td>
					<td data-col-size="sm" data-start="3008" data-end="3020">
						3,628,800
					</td>
					<td data-col-size="sm" data-start="3020" data-end="3025">
						巨大
					</td>
					<td data-col-size="sm" data-start="3025" data-end="3029">
						—
					</td>
					<td data-col-size="sm" data-start="3029" data-end="3034">
						—
					</td>
				</tr>
			</tbody>
		</table>
	</div>
</div>
<br />
<p>
	<br />
</p>
<h2 data-start="2697" data-end="2722">
	<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>⚙️ </strong></span><strong data-start="2703" data-end="2722"><span style="font-family:DFKai-SB;font-size:24px;color:#E53333;">附加：各複雜度增長對比（理論）</span></strong> 
</h2>
<div class="_tableContainer_1rjym_1">
	<div tabindex="-1" class="group _tableWrapper_1rjym_13 flex w-fit flex-col-reverse">
		<table data-start="2724" data-end="3034" class="w-fit min-w-(--thread-content-width)">
			<thead data-start="2724" data-end="2760">
				<tr data-start="2724" data-end="2760">
					<th data-start="2724" data-end="2730" data-col-size="sm">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>複雜度</strong></span> 
					</th>
					<th data-start="2730" data-end="2737" data-col-size="sm">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>n=10</strong></span> 
					</th>
					<th data-start="2737" data-end="2744" data-col-size="sm">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>n=20</strong></span> 
					</th>
					<th data-start="2744" data-end="2751" data-col-size="sm">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>n=50</strong></span> 
					</th>
					<th data-start="2751" data-end="2760" data-col-size="sm">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>n=100</strong></span> 
					</th>
				</tr>
			</thead>
			<tbody data-start="2805" data-end="3034">
				<tr data-start="2805" data-end="2829">
					<td data-start="2805" data-end="2812" data-col-size="sm">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>O(1)</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2812" data-end="2816">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>1</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2816" data-end="2820">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>1</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2820" data-end="2824">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>1</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2824" data-end="2829">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>1</strong></span> 
					</td>
				</tr>
				<tr data-start="2830" data-end="2858">
					<td data-start="2830" data-end="2841" data-col-size="sm">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>O(log n)</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2841" data-end="2845">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>3</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2845" data-end="2849">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>4</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2849" data-end="2853">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>6</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2853" data-end="2858">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>7</strong></span> 
					</td>
				</tr>
				<tr data-start="2859" data-end="2888">
					<td data-start="2859" data-end="2866" data-col-size="sm">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>O(n)</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2866" data-end="2871">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>10</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2871" data-end="2876">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>20</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2876" data-end="2881">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>50</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2881" data-end="2888">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>100</strong></span> 
					</td>
				</tr>
				<tr data-start="2889" data-end="2925">
					<td data-start="2889" data-end="2902" data-col-size="sm">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>O(n log n)</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2902" data-end="2907">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>30</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2907" data-end="2912">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>80</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2912" data-end="2918">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>282</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2918" data-end="2925">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>664</strong></span> 
					</td>
				</tr>
				<tr data-start="2926" data-end="2962">
					<td data-start="2926" data-end="2934" data-col-size="sm">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>O(n²)</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2934" data-end="2940">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>100</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2940" data-end="2946">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>400</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2946" data-end="2953">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>2500</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2953" data-end="2962">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>10000</strong></span> 
					</td>
				</tr>
				<tr data-start="2963" data-end="2999">
					<td data-start="2963" data-end="2971" data-col-size="sm">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>O(2ⁿ)</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2971" data-end="2978">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>1024</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2978" data-end="2990">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>1,048,576</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2990" data-end="2994">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>—</strong></span> 
					</td>
					<td data-col-size="sm" data-start="2994" data-end="2999">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>—</strong></span> 
					</td>
				</tr>
				<tr data-start="3000" data-end="3034">
					<td data-start="3000" data-end="3008" data-col-size="sm">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>O(n!)</strong></span> 
					</td>
					<td data-col-size="sm" data-start="3008" data-end="3020">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>3,628,800</strong></span> 
					</td>
					<td data-col-size="sm" data-start="3020" data-end="3025">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>巨大</strong></span> 
					</td>
					<td data-col-size="sm" data-start="3025" data-end="3029">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>—</strong></span> 
					</td>
					<td data-col-size="sm" data-start="3029" data-end="3034">
						<span style="font-family:DFKai-SB;font-size:24px;color:#E53333;"><strong>—</strong></span> 
					</td>
				</tr>
			</tbody>
		</table>
	</div>
</div>
<span style="font-family:DFKai-SB;font-size:24px;"><strong></strong></span><br />
<br />

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *