大 O 表示法 - Python-Python教程-PHP中文网

大 O 表示法 - Python

心靈之曲

发布： 2024-11-17 09:06:51

转载

965人浏览过

1. 定义

描述算法执行时间或空间使用上限的数学符号。它表示为 o(f(n))，其中 f(n) 是一个函数，将时间或空间表示为输入 n 大小的函数.

大 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")

登录后复制

大 O 表示法 - Python