计算递归方程输入大小的策略？

Question

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

1. 在不进行“有根据的猜测”的情况下仅从算法中得出结论
2. 确认我们没有浪费时间证明具有错误导出的输入大小的递归方程

非常感谢您的建议，提前致谢。

Answer 1

事实上，输入大小通常不是任意的。需要正确判断那是什么

那么我们该怎么做呢？

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

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

什么是蛮力法？好吧，你可以要求每一个可能的价值。什么影响复杂性？您可以选择的值的数量。那是你的输入大小。为了降低复杂性，您可能需要使用二分搜索，这样可以减少查询次数。输入大小保持不变。

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

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

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