使用 Python 視覺化 O(n)

---

介紹

瞭解演算法的效率在計算機科學和程式設計領域至關重要，因為它有助於建立既最佳化又快速執行的軟體。時間複雜度在這種情況下是一個重要的概念，因為它衡量演算法的執行時間隨著輸入規模增長而變化的方式。常用的時間複雜度類 O(n) 表示輸入大小和執行時間之間存線上性關係。

定義

在計算機科學中，演算法複雜度是對執行演算法所需資源（例如時間和空間利用率）的評估，這取決於其輸入大小。更進一步解釋，它有助於我們理解演算法在考慮其輸入大小的情況下執行速度有多快。用於描述演算法複雜度的主要符號是大 O 符號 (O(n))。

語法

for i in range(n):
   # do something

一個 `for` 迴圈多次執行特定的一組指令，由 0 到 `n−1` 的範圍指示，並在每次迭代中對迴圈內的操作或一組操作執行操作。其中 'n' 代表迭代次數。

在 O(n) 時間複雜度中，隨著我們增加輸入大小 'n'，執行時間成比例增長。隨著 'n' 的增加，迭代次數和迴圈完成所需的時間也將成比例增加。線性時間複雜度顯示輸入大小和執行時間之間存在正比例關係。

迴圈內的任何任務或任務序列都可以執行，而無需考慮輸入大小 'n'。這裡主要需要注意的是迴圈執行 'n' 次迭代，導致線性時間複雜度。

演算法

• 步驟 1：將 sum 變數初始化為 0

• 步驟 2：遍歷提供的列表中的每個元素

• 步驟 3：將元素新增到當前的 sum 值中。

• 步驟 4：迴圈結束後應返回 sum。

• 步驟 5：結束

方法

• 方法 1：繪製時間與輸入大小的關係圖

• 方法 2：繪製操作次數與輸入大小的關係圖

方法 1：繪製時間與輸入大小的關係圖

示例

import time
import matplotlib.pyplot as plt

def algo_time(n):
    sum = 0
    for i in range(n):
        sum += i
    return sum

input_sizes = []
execution_times = []

for i in range(1000, 11000, 1000):
    start_time = time.time()
    algo_time(i)
    end_time = time.time()
    input_sizes.append(i)
    execution_times.append(end_time - start_time)

plt.plot(input_sizes, execution_times)
plt.xlabel('Input Size')
plt.ylabel('Execution Time (s)')
plt.show()

輸出

此程式碼用於測量 `algo_time()` 演算法在不同輸入大小下的執行時間。我們將把我們希望測試的輸入大小以及它們各自的執行時間儲存在這些列表中。

使用 'for' 迴圈迭代一系列輸入大小。在這種情況下，迴圈將從 1000 執行到 11000 之前，每次遞增 1000。更詳細地說，我們計劃透過將 'n' 值從 1000 更改到 10000，每次遞增 1000 來評估演算法。

在迴圈內，我們測量 `algo_time()` 函式對於每個輸入大小的執行時間。為了開始跟蹤時間，我們在呼叫函式之前使用 `time.time()`，並在函式執行完成後立即停止它。然後我們將持續時間儲存在一個名為 'execution_time' 的變數中。

對於每個給定的輸入大小，我們將輸入值 ('n') 及其相應的執行時間新增到各自的列表 ('input_sizes' 和 'execution_times') 中。

迴圈完成後，我們擁有生成繪圖所需的資料。'plt.plot(input_sizes, execution_times)' 使用我們收集的資料生成一個基本的線形圖。x 軸顯示 'input_sizes' 值，表示不同的輸入大小。

'plt.xlabel()' 和 'plt.ylabel()' 最終用於標記軸，分別表示其含義，而呼叫 'plt.show()' 函式使我們能夠呈現圖表。

透過執行此程式碼，我們可以透過繪製的圖表來視覺化執行時間如何隨著較大的輸入大小 ('n') 而增加。假設演算法的時間複雜度為 O(n)，我們可以近似認為輸入大小和執行時間之間存在幾乎直線的關係。

方法 2：繪製操作次數與輸入大小的關係圖

示例

import matplotlib.pyplot as plt

def algo_ops(n):
    ops = 0
    sum = 0
    for i in range(n):
        sum += i
        ops += 1
    ops += 1  # for the return statement
    return ops

input_sizes = []
operations = []

for i in range(1000, 11000, 1000):
    input_sizes.append(i)
    operations.append(algo_ops(i))

plt.plot(input_sizes, operations)
plt.xlabel

plt.xlabel('Input Size')
plt.ylabel('Number of Operations')
plt.show()

輸出

此程式碼旨在分析 `algo_ops()` 演算法針對不同輸入大小執行的操作次數。透過使用 `algo_ops()` 函式，可以計算從零到給定輸入引數 'n' 的所有數值之和的結果，同時跟蹤和記錄在這些計算過程中執行的每個操作。

我們首先匯入 'matplotlib.pyplot' 模組，該模組允許我們建立圖表等視覺化效果。

接下來，我們定義 algo_ops() 函式，該函式接受輸入數字 'n'。在函式內部，我們初始化兩個變數：'ops' 用於計算操作次數，'sum' 用於儲存數字的累加和。

這些陣列將儲存我們想要檢查的維度及其各自的執行持續時間。

我們使用迭代迴圈的一種方法是在一組多個輸入比例內迴圈。在這種情況下，迴圈從 1000 執行到 10000（11000 除外）。這意味著我們將評估變數 'n' 從 1000 到 10000，每次遞增 100 的技術。

在迴圈內，我們計算所有輸入大小的 `algo_time()` 程式的效能。我們在呼叫程式之前使用 `time.time()` 啟動一個秒錶，並在子程式執行結束之後立即結束它。接下來，我們將時間間隔儲存在稱為 'execution_period' 的變數中。

對於每個輸入大小，我們將輸入值 ('n') 新增到名為 'input_sizes' 的列表中。此外，我們還將相應的處理時間附加到 'execution_times' 集合中。

迴圈完成後，我們已經積累了製作圖表所需的基本資料。語句 'plt.plot(input_sizes, execution_times)' 使用收集到的資料建立一個基本的線形圖。'input_sizes' 的值顯示在 x 軸上，表示不同的輸入大小。'execution_times' 的值顯示在垂直軸上，表示 `algo_time()` 函式針對不同的輸入大小執行所花費的時間。

最後，我們透過 'plt.xlabel()' 和 'plt.ylabel()' 來標記座標系，以演示每個軸的含義。接下來，執行 'plt.show()' 函式以呈現圖表。

一旦我們執行程式，圖表將向我們顯示當輸入的大小 ('n') 增加時處理時間是如何增加的。

結論

總之，掌握使用 Matplotlib 在 Python 中進行時間複雜度和視覺化對於任何尋求建立高效和最佳軟體解決方案的程式設計師來說都是一項寶貴的技能。瞭解演算法在不同輸入大小下的行為使我們能夠解決複雜問題並構建能夠及時高效地交付結果的強大應用程式。