运行 菜鸟算法时间
Running time of Algorithme for Rookies
我制作了这个伪代码
A = 2,1,8,4,3,6
n = 6
i = 1
H = 2
inv = 0
while H <= n
if A[i] > A[H] && !H = n
inv = inv + 1
H = H + 1
else if A[i] > A[H] && H = n
inv = inv + 1
i = i + 1
H = i + 1
else if A[i] < A[H] && !H = n
H = H + 1
else if A[i] < A[H] && H = n
i = i + 1
H = i + 1
print inv
现在我需要计算这个算法的 运行 时间。如果有人能和我一起一步步告诉我你是如何计算这个例子的 运行 时间的核心，我将永远感激不尽。
我阅读了很多关于这个主题的指南和书籍。都提到了成本、单位、时间、常数等。所有这些都让我更加困惑。我现在求助于你们作为最后的手段，希望能充分理解这件事。
我假设 n 是输入的大小。
请注意，在循环的每一步，H 总是增加 1。此循环将 运行 直到 H 达到 n。因此循环中的迭代次数是 n-1 因为 H 在开始时设置为 2.
此外，循环中的每个操作都是O(1)。因此程序 运行s 在 O(N).
编辑:
为了回答 Nulle 的评论，c1,c2,... 指的是常量。每个常量代表一定的时间量。例如，for 循环可能需要 c1 时间到 运行 通过循环的 1 次迭代。输出答案、初始化变量、设置循环等可能需要 c2 时间。因此 运行 花费的时间是 c1 * n + c2。我们不知道 c1 和 c2 是什么，因为它们因平台而异。更多信息，可以参考这个link
我制作了这个伪代码
A = 2,1,8,4,3,6
n = 6
i = 1
H = 2
inv = 0
while H <= n
if A[i] > A[H] && !H = n
inv = inv + 1
H = H + 1
else if A[i] > A[H] && H = n
inv = inv + 1
i = i + 1
H = i + 1
else if A[i] < A[H] && !H = n
H = H + 1
else if A[i] < A[H] && H = n
i = i + 1
H = i + 1
print inv
现在我需要计算这个算法的 运行 时间。如果有人能和我一起一步步告诉我你是如何计算这个例子的 运行 时间的核心，我将永远感激不尽。
我阅读了很多关于这个主题的指南和书籍。都提到了成本、单位、时间、常数等。所有这些都让我更加困惑。我现在求助于你们作为最后的手段，希望能充分理解这件事。
我假设 n 是输入的大小。
请注意，在循环的每一步，H 总是增加 1。此循环将 运行 直到 H 达到 n。因此循环中的迭代次数是 n-1 因为 H 在开始时设置为 2.
此外，循环中的每个操作都是O(1)。因此程序 运行s 在 O(N).
编辑:
为了回答 Nulle 的评论，c1,c2,... 指的是常量。每个常量代表一定的时间量。例如，for 循环可能需要 c1 时间到 运行 通过循环的 1 次迭代。输出答案、初始化变量、设置循环等可能需要 c2 时间。因此 运行 花费的时间是 c1 * n + c2。我们不知道 c1 和 c2 是什么，因为它们因平台而异。更多信息，可以参考这个link