问题标签 [proof]

基于比较的排序是nlog(n)的大欧米茄，所以我们知道合并排序不能是O(n)。不过，我找不到以下证明的问题：

命题P(n)：对于长度为n的列表，合并排序需要O(n)时间。

P(0)：对空列表进行合并排序只返回空列表。

强归纳：假设P(1), ..., P(n-1)并尝试证明P(n)。我们知道，在递归归并排序的每一步，两个近似“半列表”被归并排序，然后被“压缩”。通过归纳，每个半列表的合并排序需要O(n/2) 时间。拉上拉链需要O(n)时间。因此，该算法具有M(n) = 2M(n/2) + O(n)的递归关系，即2O(n/2) + O(n)即O(n)。

我在测试中弄错了这个问题，想知道是否有人可以解释它，显示得出结论所采取的步骤。任何帮助，将不胜感激。

在 L_neq = {0^i1^j | 的 PL 证明中 i < j} 给定一个 m-state DFA，有人选择字符串 0^(m/2)1^(m/2+1)。然后他们选择 y = 0 并表明通过抽水，我们可以到达 L_neq 之外的字符串 0^(m/2+1)1^(m/2+1)。这个证明正确吗？为什么或者为什么不？

此外，如果这个证明是错误的，请写下一个正确的证明。

谢谢

我需要 CLRS Algorithms 书中关于这个练习的提示：

证明无论我们从高度为 h 的二叉搜索树中的哪个节点开始，对 Tree-Successor 的k次连续调用都需要O(k+h)时间。

在大 O 表示法中O((log n)^k) = O(log n)，k某个常数（例如，对数 for 循环的数量）在哪里，是真的吗？

我的教授告诉我这个说法是正确的，但是他说这将在课程的后期得到证明。我想知道你们中的任何人是否可以证明它的有效性或有一个链接我可以确认它是否属实。

证明对于任何实数 a, b 使得 a > b > 0, b^n 是 O(a^n), n >=1。

我已经搜索了我拥有的几本关于离散数学的教科书以及几个在线搜索，以查找与此证明相关的任何相似示例或定理。我不是在寻找直接的解决方案，而是可能被展示了解决证明的正确方法或范式。

有人可以带我了解以下问题解决方案的数学部分。

证明没有比较排序，其运行时间至少在 n 的一半内是线性的！长度为 n 的输入。那么长度为 n 的输入的 1/n 的一部分呢？分数 (1/(2)^n) 怎么样？

解决方案：

如果排序以线性时间运行 m 个输入排列，则由 m 个对应叶子及其祖先组成的决策树部分的高度 h 是线性的。使用与定理 8.1 证明中相同的论证来证明对于 m = n!/2、n!/n 或 n!/2n 这是不可能的。我们有 2^h ≥ m，这给了我们 h ≥ lgm。对于此处给出的所有可能的 ms，lgm = Ω(n lg n)，因此 h = Ω(n lg n)。尤其是，

我编写了自己的琐碎小函数（为方便起见是 php），并希望有人可以通过归纳来帮助构造一个证明，这样我就可以掌握它的一个非常基本的窍门。

结果是每个索引处的值与索引本身相同，但这只是因为 a[0] 被初始化为 0。

我相信目标是（或应该是）证明不变量（它本身可能是可疑的，但希望能得到理解）适用于 k+1。

谢谢

编辑：示例：http ://homepages.ius.edu/rwisman/C455/html/notes/Chapter2/LoopInvariantProof.htm

我使用了这个加权随机数生成器。

如下：

我经常在结果中看到7, 8, 9, 10。

是否有一些证据或保证这对概率论是正确的？

(log n)^k = O(n)? For k greater or equal to 1.

我的教授在课堂上向我们展示了这个陈述，但是我不确定时间复杂度为 O(n) 的函数意味着什么。即使是这样的东西n^2 = O(n^2)，函数 f(x) 怎么会有运行时复杂度？

至于语句如何等于 O(n) 而不是 O((logn)^k)？