如何计算创建算法的理论 运行 时间？
How to calculate theoretical running time for a created algorithm?
我需要一些帮助来分析我的算法以确定其理论上的 运行宁时间。我想我了解如何分析其中的大部分内容。我不确定如何分析包含 for 循环 的 while 循环。我将提供我的算法，然后是我 think/know.
我的算法：
def getD(a):
corrections = [] #list for correction values
comparisons = 0 #comparison counter
#initialize corrections list with all 0's
for i in range(0,len(a)):
corrections.append(0)
flag = True #loop control
while(flag):
flag = False
#loop through list
for i in range(0,len(a)-1):
current = a[i] #current element value
nxt = a[i+1] #next element value
dif = nxt - (current + 1)
#correct the nxt item.. i+1. comparisons++
if(dif < 0):
comparisons += 1
corrections[i+1] -= dif
a[i+1] -= dif
flag = True
d = int((max(corrections)+1)/2)
#balance the corrections
for i in range(len(a)):
corrections[i] -= d
print(d)
print("Number of comparisons:",comparisons)
我的进度分析：
n = 输入列表的长度 (a)
主要操作是 3 个 for 循环和 while 循环。
第一个 for 循环 迭代 n 次.. 所以它的 运行ning 时间为 n.
最后一个 for 循环也迭代 n 次.. 对每个元素应用校正，因此它也有 n 的 运行ning 时间。
对于上面的 2 for 循环.. 我认为合并的 运行ning 时间应该是 2n？但是整个算法还有更多内容需要添加 运行宁时间。
这是我开始挣扎的地方：
剩下的主要操作（我相信）是 while 循环和 for 循环 inside.The for 循环将 运行 至多 n-1 次。但是如果 dif < 0，它 运行 再次从 i=0 开始的 for 循环。
我不确定这部分的 运行 时间或整个算法。如何计算其中包含最后一个 for 循环的 while？我如何将它们组合在一起？
您的第一个 for 循环总是 运行s 进行 n 次迭代，因此是 O(n)。
你的最后一个 for 循环总是 运行s 进行 n 次迭代，因此是 O(n)。
你的中间 for 循环（在 while 循环内）总是 运行s 进行 n - 1 次迭代，因此是 O(n)。
现在，while 循环将执行多少次迭代？它看起来是可变的，但让我们仔细看看内部 for 循环：
for i in range(0,len(a)-1):
current = a[i] #current element value
nxt = a[i+1] #next element value
dif = nxt - (current + 1)
#correct the nxt item.. i+1. comparisons++
if(dif < 0):
comparisons += 1
corrections[i+1] -= dif
a[i+1] -= dif
flag = True
因此，在第一次通过此 for 循环时，i == 0。 if 语句通过在必要时设置 a[1] = a[0] + 1 来确保 a[1] ≥ a[0] + 1。
第二遍，i == 1。 if 语句通过在必要时设置 a[2] 来确保 a[2] ≥ a[1] + 1。
第三遍，i == 2。 if 语句通过在必要时设置 a[3] 来确保 a[3] ≥ a[2] + 1。
请注意，在每次循环中，循环都可以设置 a[i+1]，但不能设置更早的元素。因此，每次通过内部 for 循环都无法撤消前一次通过的工作。
当此内部 for 循环停止执行时，a[i+1] ≥ a[i] + 1 对所有 i。
while 循环保证至少 运行 一次。如果内部 for 循环对数组进行了任何更改，它会设置 flag，从而使 while 循环再次执行。在第二次通过 while 循环时，数组已经完全整理，因此 flag 将保持 False.
因此while循环最多执行两次迭代，所以它是O(2n)（n来自内部for循环的O(n)复杂度）。你可能知道 O(2n) == O(n).
你的 getD 函数中的所有外部循环都是 O(n)，所以你的函数本身就是 O(n)。
顺便说一句，你可以在Python中像这样初始化corrections:
corrections = [0] * len(a)
我需要一些帮助来分析我的算法以确定其理论上的 运行宁时间。我想我了解如何分析其中的大部分内容。我不确定如何分析包含 for 循环 的 while 循环。我将提供我的算法，然后是我 think/know.
我的算法：
def getD(a):
corrections = [] #list for correction values
comparisons = 0 #comparison counter
#initialize corrections list with all 0's
for i in range(0,len(a)):
corrections.append(0)
flag = True #loop control
while(flag):
flag = False
#loop through list
for i in range(0,len(a)-1):
current = a[i] #current element value
nxt = a[i+1] #next element value
dif = nxt - (current + 1)
#correct the nxt item.. i+1. comparisons++
if(dif < 0):
comparisons += 1
corrections[i+1] -= dif
a[i+1] -= dif
flag = True
d = int((max(corrections)+1)/2)
#balance the corrections
for i in range(len(a)):
corrections[i] -= d
print(d)
print("Number of comparisons:",comparisons)
我的进度分析：
n = 输入列表的长度 (a)
主要操作是 3 个 for 循环和 while 循环。
第一个 for 循环 迭代 n 次.. 所以它的 运行ning 时间为 n.
最后一个 for 循环也迭代 n 次.. 对每个元素应用校正，因此它也有 n 的 运行ning 时间。
对于上面的 2 for 循环.. 我认为合并的 运行ning 时间应该是 2n？但是整个算法还有更多内容需要添加 运行宁时间。
这是我开始挣扎的地方：
剩下的主要操作（我相信）是 while 循环和 for 循环 inside.The for 循环将 运行 至多 n-1 次。但是如果 dif < 0，它 运行 再次从 i=0 开始的 for 循环。
我不确定这部分的 运行 时间或整个算法。如何计算其中包含最后一个 for 循环的 while？我如何将它们组合在一起？
您的第一个 for 循环总是 运行s 进行 n 次迭代，因此是 O(n)。
你的最后一个 for 循环总是 运行s 进行 n 次迭代，因此是 O(n)。
你的中间 for 循环（在 while 循环内）总是 运行s 进行 n - 1 次迭代，因此是 O(n)。
现在，while 循环将执行多少次迭代？它看起来是可变的，但让我们仔细看看内部 for 循环：
for i in range(0,len(a)-1):
current = a[i] #current element value
nxt = a[i+1] #next element value
dif = nxt - (current + 1)
#correct the nxt item.. i+1. comparisons++
if(dif < 0):
comparisons += 1
corrections[i+1] -= dif
a[i+1] -= dif
flag = True
因此，在第一次通过此 for 循环时，i == 0。 if 语句通过在必要时设置 a[1] = a[0] + 1 来确保 a[1] ≥ a[0] + 1。
第二遍，i == 1。 if 语句通过在必要时设置 a[2] 来确保 a[2] ≥ a[1] + 1。
第三遍，i == 2。 if 语句通过在必要时设置 a[3] 来确保 a[3] ≥ a[2] + 1。
请注意，在每次循环中，循环都可以设置 a[i+1]，但不能设置更早的元素。因此，每次通过内部 for 循环都无法撤消前一次通过的工作。
当此内部 for 循环停止执行时，a[i+1] ≥ a[i] + 1 对所有 i。
while 循环保证至少 运行 一次。如果内部 for 循环对数组进行了任何更改，它会设置 flag，从而使 while 循环再次执行。在第二次通过 while 循环时，数组已经完全整理，因此 flag 将保持 False.
因此while循环最多执行两次迭代，所以它是O(2n)（n来自内部for循环的O(n)复杂度）。你可能知道 O(2n) == O(n).
你的 getD 函数中的所有外部循环都是 O(n)，所以你的函数本身就是 O(n)。
顺便说一句，你可以在Python中像这样初始化corrections:
corrections = [0] * len(a)