algorithm - 计算递推方程输入大小的策略？

Question

我正在努力寻找一种精确的方法来了解我们的尺寸n应该如何定义。证明我的意思；以二进制搜索为例。的输入大小定义n为。我真的不明白我们怎么能T(n)high - low + 1

1. 仅从算法中找出答案，而无需进行“有根据的猜测”
2. 确认我们没有浪费时间用错误导出的输入大小证明递归方程

我真的很感激一些建议，在此先感谢。

标签： algorithmrecursionrecurrenceproof

Answer 1

实际上，输入大小通常不是任意的。有必要正确确定那是什么。

那么我们该怎么做呢？

首先，您必须了解该算法 - 它的作用以及您为什么要使用它。通常你可以很容易地暴力破解任何问题，但你仍然决定使用更好的东西。为什么？回答这个问题应该让一切都清楚。

让我们看一下您的二进制搜索示例。你想通过调用一个单调函数来找到一个特定的值，这个函数会告诉你你的选择是太低还是太高。例如，您可能希望在数组中找到小于特定数字的最大值。

什么是蛮力方法？好吧，您可以要求所有可能的值。什么影响复杂性？您可以选择的值的数量。那是您的输入大小。为了降低复杂性，您可能希望使用二分搜索，它可以让您执行更少的查询。输入大小保持不变。

让我们看看其他一些算法：

• GCD的欧几里得算法 - 蛮力？搜索小于或等于输入最小值的每个数字。什么影响复杂性？您要检查的值的数量，即您要为其查找 GCD 的数字。
• BFS/DFS（图遍历）——你想访问每个节点一次。对于每个节点，您必须另外检查每条边。总而言之：输入大小是节点和边的数量。
• KMP/Karp-Rabin/任何其他模式查找算法 - 您想查找文本中出现的模式，输入大小显然是文本大小，也是模式大小。

一旦你理解了算法解决的问题，就可以考虑一种蛮力方法。确定影响速度的因素，可以改进的因素。这很可能是您的输入大小。在更复杂的情况下，输入大小在算法的描述中说明。