python - 我如何证明和分析代码的运行时间,是 O(n) 吗?
问题描述
如何通过递归调用证明和分析代码的运行时间,是 O(n) 吗?
A = [10,8,7,6,5]
def Algorithm(A):
ai = max(A) # find largest integer
i = A.index(ai)
A[i] = 0
aj = max(A) # finding second largest integer
A[i] = abs(ai - aj) # update A[i]
j = A.index(aj)
A[j] = 0 # replace the A[j] by 0
if aj == 0: # if second largest item equals
return ai # to zero return the largest integer
return Algorithm(A) # call Algorithm(A) with updated A
解决方案
起初,我有点怀疑你的算法是否真的在 O(n) 中运行。还有以下程序
import timeit, random
import matplotlib.pyplot as plt
code = """
def Algorithm(A):
ai = max(A) # find largest integer
i = A.index(ai)
A[i] = 0
aj = max(A) # finding second largest integer
A[i] = abs(ai - aj) # update A[i]
j = A.index(aj)
A[j] = 0 # replace the A[j] by 0
if aj == 0: # if second largest item equals
return ai # to zero return the largest integer
return Algorithm(A) # call Algorithm(A) with updated A
Algorithm(%s)
"""
x, y = [], []
lst = [random.randint(-1000, 10000)]
for i in range(1000):
lst.append(random.randint(-1000, 10000))
time = timeit.timeit(stmt=code % lst, number=10)
x.append(i)
y.append(time)
plt.plot(x, y)
plt.show()
测量不同随机生成列表的算法运行时间(然后绘制此图)。结果
显然支持非线性增长。所以说否则,因为该算法的复杂度为 O(n^2),因此无法证明它在 O(n) 内运行。
推荐阅读
- javascript - Symfony/Encore/Webpack 中的运行时按钮 onclick 事件处理函数
- c++ - 函数返回的值会导致堆栈溢出吗?
- css - 来自模块的 React css 不适用(没有 webpack)
- oracle - 在 Oracle DB 的另一个模式中重新编译同义词
- swift - SwiftUI 核心数据
- azure-devops - azure-devops-extension-api - 运行管道
- macos - X2Go 客户端无法启动 X11 服务器。(macOS 卡塔利娜)
- javascript - 使用 jQuery 将克隆的节点添加到 DOM
- javascript - 过滤数组的对象并返回参数
- c# - LINQ 表达式 DbSet
无法翻译