一个算法的效率是否可以被建模为输入大小和时间之间的函数？

Question

考虑以下算法（只是作为一个例子，因为其实现显然是低效的）。

def add(n):
    for i in range(n):
        n += 1
return n

程序将一个数字与自己相加并返回。现在算法的效率是 有时 建模为输入大小与算法所需计算的原始步数之间的函数。在这种情况下，输入是一个整数n，随着n的增加，完成算法所需的步数也会增加（在这种情况下是线性的）。但输入的大小真的会增加吗？我们假设程序运行的机器是用8位来表示整数的。因此，如果我将hypthetical输入3增加到7，涉及的位数保持不变：000011 -> 00000111。但是，计算算法所需的步骤却增加了。所以，看来算法效率并不总是真的可以被建模为输入大小和计算步骤之间的关系。谁能给我解释一下我错在哪里，或者如果我没有错，为什么把算法的效率建模为输入大小和要计算的基元步数之间的函数还是有意义的？

Answer 1

让 S 是输入的大小 n. (通常我们会用 n 为这个大小，但由于参数也被称为 n，这很令人困惑）。) 对于正 n，有一个关系是 S 和 n即 S = ceil(ln(n)). 程序循环 n 次，而自 n < 2^S循环，它最多循环 2^S 次。你还可以显示它至少循环了12*2^S次，所以运行时间（以循环迭代为单位）是 Theta(2^S).

这说明有一种方法可以将运行时间建模为大小的函数，即使它不精确。

是否有意义。在你的例子中，它没有多大意义，但如果你的输入是一个用于排序的数组，把大小作为数组中元素的数量确实有意义。(而且一般都是比如用来模拟不同排序算法所做的比较次数的)。