如何计算算法的增长率和时间量？

Question

我目前正在欣赏 Allen Downey 的 Think Complexity，几个小时前我完成了关于增长率的部分。我暂停了阅读和 googled 增长率，并扩展了这本书给我的信息。我还发现，您可以计算算法计算原始数据所需的 time 量。我有很多 google 无法回答的问题，或者我的回答可能需要个人风格，因为它确实有助于我理解。我的问题是：

1-一个简单的算法怎么可能算出增长率？例如，我刚刚编写了这个循环来使用泰勒级数计算给定角度的正弦弧度：

    for i in range(0, 360):
        return sum(((-1)**i / (factorial((2 * i) + 1))) * d ** ((2*i) + 1))

和阶乘：

def factorial(n):
    factorial = 1
    for i in range(1, n+1):
        factorial *= i

return factorial

如何计算它的增长率？

2- 我熟悉了一些非常糟糕的算法，比如 Bogosort。使用 bogosort 对数组进行排序需要花费大量时间。但是你如何计算时间呢？它因计算机而异。

3-什么是Big-O符号，它与增长率有什么关系？

感谢您的回答。

Answer 1

通常情况下，计算一个函数所花费的时间并不是一个好的方法，因为它取决于许多因素。出于这个原因，我们经常用计算步骤来表达复杂性。

存在多种表示法（big-Oh、big-Omega、big-Theta）。 Big-Oh 表示上限，因此 O(n) 表示在最坏情况下它将执行 n 个步骤。

Big-Omega (Ω) 是下限，因此 Ω(n) 表示最少 n 步。两者的组合是 big-theta Ө，因此，Ө(n) 表示它将正好执行 n 步。

在您的例子中，factorial 定义为

def factorial(n):
    factorial = 1
    for i in range(1, n+1):
        factorial *= i

return factorial

这个函数将从1到n+1循环一次，因此，它取决于它的参数n。我们可以说它将恰好执行 n 步，因此，我们可以说 factorial 在 Ө(n) 中。请注意，这显然是线性的。

如何计算算法的增长率和时间量？

How to calculate the growth rate, and time amount of an algorithm?

python

algorithm

time

complexity-theory