通过证明递归是 Omega(nlogn) 来归纳证明递归不是 O(n)
Inductive Proof that a recurrence isn't O(n) by showing it is Omega(nlogn)
注：这个跟作业有关
我试图证明 T(n/3) + T(2n/3) + n >= cn , for all c > 0。
当我尝试这样做时，基本案例失败了 (T(1) = 1 >= cn, for all c > 0，这不是真的）。所以为了解决这个问题，我想证明问题的下限高于 O(n)。这是否构成正确的证明？
作为提示，请尝试添加更多术语。假设你的函数满足
T(n) ≥ k1n log n + k2n + k3
现在，当您插入 n = 1 时，可以通过设置 k2 和 k3[=17= 使右侧非零】 恰到好处。这种技术在对上界和下界函数进行归纳时很常见，并且之所以有效，是因为这些低阶项与大 O 表示法无关，可以优雅地处理较小的情况。
注：这个跟作业有关
我试图证明 T(n/3) + T(2n/3) + n >= cn , for all c > 0。
当我尝试这样做时，基本案例失败了 (T(1) = 1 >= cn, for all c > 0，这不是真的）。所以为了解决这个问题，我想证明问题的下限高于 O(n)。这是否构成正确的证明？
作为提示，请尝试添加更多术语。假设你的函数满足
T(n) ≥ k1n log n + k2n + k3
现在，当您插入 n = 1 时，可以通过设置 k2 和 k3[=17= 使右侧非零】 恰到好处。这种技术在对上界和下界函数进行归纳时很常见，并且之所以有效，是因为这些低阶项与大 O 表示法无关，可以优雅地处理较小的情况。