大O表示法
1. 定义
描述算法执行时间或空间使用上限的数学符号。它表示为 o(f(n))，其中 f(n) 是一个函数，将时间或空间表示为输入 n 大小的函数.
更多信息请访问：bigocheatsheet.
. 目的算法比较：允许您比较不同的算法并针对给定问题选择最有效的算法。可扩展性：帮助预测当数据量增加时算法的行为方式。3. 复杂度分析最坏情况：指算法耗时更长或使用更多资源的场景。大o通常指的是这种情况。最佳情况和平均情况：虽然很重要，但它们在大 o 表示法中使用频率较低。4.空间与空间时间时间复杂度：指算法执行所需的时间。空间复杂度：指的是它使用的额外内存量。它可以具有诸如 o(1)（恒定空间）或 o(n)（线性空间）之类的符号。
示例：
import timeitimport matplotlib.pyplot as pltimport 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 timeitdef measure_time(func, *args): execution_time = timeit.timeit(lambda: func(*args), number=1000) return execution_timedef 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的详细内容，更多请关注范的资源库其它相关文章！
