大 O 表示法 - Python-Python教學-PHP中文網

大 O 表示法 - Python

Barbara Streisand

發布： 2024-11-18 08:43:01

原創

732 人瀏覽過

1. 定義

描述演算法執行時間或空間使用上限的數學符號。它表示為O(f(n))，其中f(n) 是一個函數，將時間或空間表示為輸入n 大小的函數.

Notación Big O - Python
更多資訊請見：http://bigocheatsheet.com

2. 目的

演算法比較：讓您比較不同的演算法並針對給定問題選擇最有效的演算法。
可擴展性：幫助預測當資料量增加時演算法的行為。

3. 複雜度分析

最壞情況：指演算法耗時更長或使用更多資源的場景。大O通常指的是這種情況。
最佳情況和平均情況：雖然很重要，但它們在大 O 表示法中使用頻率較低。

4.空間與空間時間

時間複雜度：指演算法執行所需的時間。
空間複雜度：指的是它使用的額外記憶體量。它可以具有諸如 O(1)（恆定空間）或 O(n)（線性空間）之類的符號。

範例：

import timeit
import matplotlib.pyplot as plt
import cProfile

# O(1)


def constant_time_operation():
    return 42

# O(log n)


def logarithmic_time_operation(n):
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

# O(n)


def linear_time_operation(n):
    total = 0
    for i in range(n):
        total += i
    return total

# O(n log n)


def linear_logarithmic_time_operation(n):
    if n <= 1:
        return n
    else:
        return linear_logarithmic_time_operation(n - 1) + n

# O(n^2)


def quadratic_time_operation(n):
    total = 0
    for i in range(n):
        for j in range(n):
            total += i + j
    return total

# O(2^n)


def exponential_time_operation(n):
    if n <= 1:
        return 1
    else:
        return exponential_time_operation(n - 1) + exponential_time_operation(n - 1)

# O(n!)


def factorial_time_operation(n):
    if n == 0:
        return 1
    else:
        return n * factorial_time_operation(n - 1)

# Function to measure execution time using timeit

def measure_time(func, *args):
    execution_time = timeit.timeit(lambda: func(*args), number=1000)
    return execution_time


def plot_results(results):
    functions, times = zip(*results)

    colors = ['skyblue', 'orange', 'green', 'red', 'purple', 'brown', 'pink']
    plt.figure(figsize=(14, 8))
    plt.bar(functions, times, color=colors)

    for i, v in enumerate(times):
        plt.text(i, v + 0.5, f"{v:.6f}", ha='center',
                 va='bottom', rotation=0, color='black')

    plt.xlabel('Function Complexity')
    plt.ylabel('Average Time (s)')
    plt.title('Execution Time of Different Algorithm Complexities')
    plt.grid(axis='y', linestyle='--', linewidth=0.5, color='gray', alpha=0.5)

    plt.tight_layout()
    plt.show()


def main():
    results = []
    results.append(("O(1)", measure_time(constant_time_operation)))
    results.append(("O(log n)", measure_time(logarithmic_time_operation, 10)))
    results.append(("O(n)", measure_time(linear_time_operation, 10)))
    results.append(("O(n log n)", measure_time(
        linear_logarithmic_time_operation, 10)))
    results.append(("O(n^2)", measure_time(quadratic_time_operation, 7)))
    results.append(("O(2^n)", measure_time(exponential_time_operation, 7)))
    results.append(("O(n!)", measure_time(factorial_time_operation, 112)))

    plot_results(results)


if __name__ == '__main__':
    cProfile.run("main()", sort="totime", filename="output_profile.prof")

登入後複製

Notación Big O - Python