1. 定义
描述算法执行时间或空间使用上限的数学符号。它表示为 o(f(n))，其中 f(n) 是一个函数，将时间或空间表示为输入 n 大小的函数.
更多信息请访问：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")
请记住，仅仅应用大符号是不够的，或者，尽管这是第一步，还有其他方法来优化内存，例如使用插槽、缓存、线程、并行性、流程等
感谢您的阅读！！
通过反应并提出您的意见来支持我。
