量級對實際程式的影響

看完昨天一大堆的數學後，我自己都寫得有點頭昏眼花了XD，但是理論也不能脫離現實，因此本段會實際用程式展示一下不同量級對於時間帶來的影響！

相信有人看到剛剛的一些複雜度函數會忍不住想：「真的有複雜度這麼奇怪的演算法嗎？」

下面就要展示，它真的存在
以下令 為複雜度函數：

long long f1(long long n) {
    long long result = 0;
    while (n) {
        result += n;
        n /= 2;
    }
    return result;
}

long long f2(long long n) {
    long long result = 0;
    for (long long i = 1; i * i <= n; ++i) {
        result += i;
    }
    return result;
}

long long f3(long long n) {
    long long result = 0;
    for (long long i = 1; i <= n; ++i) {
        result += i;
    }
    return result;
}

long long f4(long long n) {
    long long result = 0;
    for (long long i = 1; i <= n; ++i) {
        for (long long j = 1; i * j <= n; ++j) {
            result += j;
        }
    }
    return result;
}

long long f5(long long n) {
    long long result = 0;
    for (long long i = 1; i <= n; ++i) {
        for (long long j = 1; j <= n; ++j) {
            result += j;
        }
    }
    return result;
}

long long f6(long long n) {
    long long result = 0;
    for (long long i = 1; i <= n; ++i) {
        for (long long j = 1; j <= n; ++j) {
            for (long long k = 1; k <= n; ++k) {
                result += k;
            }
        }
    }
    return result;
}

long long f7(long long n) {
    if (n <= 0) return 1;
    return f7(n - 1) + f7(n - 1);
}

long long f8(long long n) {
    if (n <= 0) return 1;
    return f8(n - 1) + f8(n - 1) + f8(n - 1);
}

long long f9(long long n) {
    if (n <= 1) return 1;
    long long result = 0;
    for (int i = 1; i <= n; ++i) {
        result += f9(n - 1);
    }
    return result;
}

以上的程式有特別設計過，盡量使步驟數能精準貼近它的複雜度函數，因此函數本身沒有什麼意義，單純為了展示速度的差異而已ww

其中有些地方初學者可能會覺得「蛤？為什麼這樣寫複雜度函數就是XXX」，那是正常的！但我這邊暫時不會過多解釋，那部分之後的文章才會提到，請各位稍微耐心等待幾天。請放心，這部分保證會提到的！

有了程式，我們可以開始來比較執行時間了
不過只是單純比較也太無聊了，所以我們來用比賽的方式比較吧！

天下第一速道會——10秒殊死鬥

• 比賽規則：每一輪所有參賽程式都會待在同一個程式內測量速度，若當下所有參賽函數能成功跑完，則輸入規模提高進入下一階段；若程式執行時間超過 10 秒，則將本身執行時間就會大於 10 秒的參賽選手淘汰；若不存在本身執行時間超過 10 秒的選手，則根據剩下選手的執行時間來排序名次。

為公平起見，競賽平台將選用知名程式競技平台 Atcoder 的 Custom Test 功能，且編譯器採用 C++ 23（gcc 12.2）

要先註冊 Atcoder 的帳號才可測試

測試程式將採用如下形式：

// 第一行關閉所有編譯器優化
#pragma GCC optimize("O0")
// 第二行使編譯器只能生成通用架構的cpu指令，使對於特定cpu的優化不能使用
#pragma GCC target("tune=generic")

#include <iostream>
#include <iomanip>
#include <chrono>

// 計時函式，參數分別為(函式、函式參數、重複次數)
template<typename Func, typename Arg, typename ResultType = decltype(std::declval<Func>()(std::declval<Arg>()))>
double timer(Func&& func, Arg&& arg, int repetitions = 10) {
    std::chrono::microseconds sum(0);
    ResultType result{};
    
    for(int i = 0; i < repetitions; ++i) {
        auto start = std::chrono::high_resolution_clock::now();
        result += std::forward<Func>(func)(std::forward<Arg>(arg));
        auto end = std::chrono::high_resolution_clock::now();
        sum += std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    }
    
    std::cout << result << "\n";

    auto average_duration = std::chrono::duration<double, std::micro>(sum) / repetitions;

    return average_duration.count();
}

// 選手預備位置
long long f1(long long n);
long long f2(long long n);
long long f3(long long n);
long long f4(long long n);
long long f5(long long n);
long long f6(long long n);
long long f7(long long n);
long long f8(long long n);
long long f9(long long n);

int main() {
    std::cout << std::fixed << std::setprecision(6) << std::left;
    #define NAME(func) (#func)
    
    // 本關輸入與選手數量
    constexpr long long n = 1;
    constexpr int player = 9;
    constexpr int repetitions = 10;
    
    // 選手競賽區
    std::pair<std::string, double> r[player] = {
      {NAME(f1), timer(f1, n, repetitions)},
      {NAME(f2), timer(f2, n, repetitions)},
      {NAME(f3), timer(f3, n, repetitions)},
      {NAME(f4), timer(f4, n, repetitions)},
      {NAME(f5), timer(f5, n, repetitions)},
      {NAME(f6), timer(f6, n, repetitions)},
      {NAME(f7), timer(f7, n, repetitions)},
      {NAME(f8), timer(f8, n, repetitions)},
      {NAME(f9), timer(f9, n, repetitions)},
    };
    
    // 輸出計時結果
    std::cout << "n = " << n << std::endl;
    std::cout << "repetitions = " << repetitions << std::endl;
    for (int i = 0; i < player; ++i) {
      std::cout << r[i].first << " 累計用時: " << r[i].second << " µs(微秒)" << std::endl;
    }
    return 0;
}

// 選手休息區(想自己測就把上面的函式貼下來)

主辦方秉持公平、公正、公開的原則，將一切可能導致不公平的要素摒除，諸如編譯優化、針對特定環境的指令集等不易掌控的變因都已排除。

看不懂上面的測試程式很正常，因為大部分的東西在寫演算法的程式時基本用不上，不過編譯優化、針對特定環境的指令集等我之後文章會再提及，一樣請各位先期待一下囉~

並且基於每位選手的潛力，以下為主辦方針對賽制精心設計之 17 個輸入規模關卡，期待每位選手都能過五關斬六將，奪得最終勝利！

輸入(n)：
1
5
10
15
20
25
30
100
500
1,000
10,000
100,000
100,000,000
500,000,000
1,000,000,000
5,000,000,000
1,000,000,000,000,000,000

關於 10 秒的限制，由 Atcoder 平台的 custom test來控制，因為它被設定為執行時間超過 10 秒就會強制中斷程式，可以以此判斷是否逾越時間，之後就可以分開檢查究竟是哪個選手導致超時。

另外關於計時函式的第三個參數：重複次數，可由裁判依據當下輸入規模自由調整，不過該調整對於所有選手是統一的。

為了避免紀錄過於冗長，比賽結果的展示將採用放上結果表格，x 軸表示選手名次、y 軸為輸入規模，表格內代表對應的執行時間，時間單位為微秒，小數點以下四捨五入。

結果

單位小提醒：1 s(秒) = 1,000 ms(毫秒) = 1,000,000 µs(微秒)

先幫大家回憶一下每個選手的複雜度函數：

再對照上面的比賽結果，可以發現到其實大家一開始時間都一樣，但是隨著輸入慢慢的增長，有些選手的時間就會開始「暴衝」，突然超高速往上飆，然後過個一兩輪就被淘汰了、相反的，有些選手就表現地相當 chill，不論輸入怎麼上升，都只是意思意思增加個幾微秒，有的甚至根本不動。

其實這是可以單純透過計算來解釋的！

以 為例，它的複雜度函數是階乘，因為 這種步驟數對電腦來說幾乎是一瞬間就跑完了，因此執行時間 0 µs；但是當來到 ，雖然還在接受範圍內，但是已經沒辦法像以前一樣瞬間結束了，所以跑了 16,475 µs；最後到了 ，這種程度短短十秒內根本不可能跑完，因此它被淘汰了

這就是量級的可怕之處！
我覺得此時非常適合貼一張維基百科時間複雜度頁面的圖片：

順道一提，可以觀察到複雜度函數為線性函數的 ，因為它在輸入到 500,000,000 時的時間約為 1.189 秒，因此可以推測Atcoder Custom Test 的主機在去除所有優化和針對特定環境的指令集後的速度大約是 500,000,000 個步驟/秒。

事實上很多生活中常見的筆電、桌機、伺服器等的單核心的速度也大約可以用 步驟數/秒來估計（當然情況允許還是要自己測一下比較好）。

因此以後當你看到或聽到某某演算法的時間複雜度是XXX時，你就可以對朋友耍帥：「當輸入為OOO時要跑 1 秒...渣渣...」

回歸正題，我們現在已經能認知到不同時間複雜度的演算法在真實機器跑起來的時間大概會長怎樣？也了解到了複雜度函數對於程式運行時間的影響有多大。

但是我們剛剛的測試都是在一個非常理想的環境，複雜度函數很單純、演算法的複雜度因為不同的輸入而變動，而且重點是我們雖然知道怎麼用數學來比較不同複雜度函數的量級，但是兩天前最後面說的『忽略一些沒那麼重要的因子的「估計」方法』呢？這部分就是我們明天的課題了。