使用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：將該元素合併到目前的總和值。

• 第四步：循環結束後應傳回總和。

• 步驟 5：結束

#方法

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

• 方法二：繪製運算與輸入規模之間的關係

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

Example

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。進一步說明，我們計劃透過改變從1000到10000的'n'值來評估演算法，增量為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)，我們可以近似認為當繪製圖表時，輸入大小和執行時間之間幾乎有直線的相關性。

方法二：繪製運算與輸入大小的關係

Example

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中的時間複雜度和視覺化是任何尋求創建高效和優化軟體解決方案的程式設計師的寶貴技能。了解演算法在不同輸入規模下的行為，使我們能夠解決複雜問題並建立健壯的應用程序，以及及時有效地提供結果。

以上是使用Python可視化O(n)。的詳細內容。更多資訊請關注PHP中文網其他相關文章！