程序效率：算法与实现

Question

我在看一个关于程序效率的讲座，教授说：

"如果我测量运行ning 时间，它肯定会随着算法的变化而变化。(...) 但问题之一是它也会随着实现的函数而变化 (. ..) 如果我使用的循环在一种算法中比另一种算法多了几个步骤，它会改变时间。"

我很难理解实施的影响。

所以我的问题是：为什么我们不能在一种算法中考虑那些额外的循环步骤，与另一种算法相比，只是它运行所必需的东西，这也是一部分算法的效率？还是我完全忽略了这里的重点？

谢谢！

Answer 1

他们指出“算法”和“用编程语言编写的特定代码”之间的区别。 “算法”是一个有点模糊的术语，“算法”通常在 pseudo-code 中描述，可能非常详细，也可能根本不详细。

例如，考虑下面的算法，来测试一个数 n 是否是质数：

如果 2 和 n 的平方根之间的任意数 d 除 n:
Return 假（n 不是质数）
其他:
Return 正确（n 是质数）

你如何精确地遍历 2 和平方根之间的数字？你可以这样做：

// IMPLEMENTATION A

bool is_prime(int n)
{
    int s = sqrt(n);
    for (int d = 2; d <= s; d++)
    {
        if (n % d == 0)
            return false;
    }
    return true;
}

或：

// IMPLEMENTATION B

bool is_prime(int n)
{
    for (int d = 2; d * d <= n; d++)
    {
        if (n % d == 0)
            return false;
    }
    return true;
}

这两个代码都实现了我描述的算法。但是，它们可能具有不完全相同的运行时间，因为前者需要计算一次 sqrt(n)，而后者需要在循环中的每次迭代中计算 d * d。

计算机科学家希望能够讨论我在 pseudo-code 中描述的算法的复杂性。而且他们不希望有人给出无聊的答案“抱歉，那个算法的复杂度是无法计算的，因为我们不知道它是实现 A 还是实现 B”。

程序效率：算法与实现

Program efficiency: Algorithm vs Implementation

algorithm

implementation

terminology