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")
请记住，仅仅应用大符号是不够的，或者，尽管这是第一步，还有其他方法来优化内存，例如使用插槽、缓存、线程、并行性、流程等
感谢您的阅读！！
通过反应并提出您的意见来支持我。
