阿里淘天一面

gpt的答案： 这是一个递归方程，通常可以使用递归展开、主定理（Master Theorem）或递归树来求解。在这个情况下，我们可以使用递归展开来求解。 递归方程为： T(n) = 2 * T(n / 2) + (n - 1) 首先，我们可以展开第一层递归： T(n) = 2 * (2 * T(n / 4) + (n / 2 - 1)) + (n - 1) = 4 * T(n / 4) + 2 * (n / 2 - 1) + (n - 1) 然后，展开第二层递归： T(n) = 4 * (2 * T(n / 8) + (n / 4 - 1)) + 2 * (n / 2 - 1) + (n - 1) = 8 * T(n / 8) + 4 * (n / 4 - 1) + 2 * (n / 2 - 1) + (n - 1) 继续展开 k 层递归后，得到： T(n) = 2^k * T(n / 2^k) + k * (n / 2^k - 1) + (n - 1) 当递归到基本情况时，n / 2^k = 1，解得 k = log2(n)。 代入 k 值，得到： T(n) = 2^log2(n) * T(1) + log2(n) * (n / 2^log2(n) - 1) + (n - 1) = n * T(1) + log2(n) * (n - 1) + (n - 1) = n * T(1) + n * log2(n) - log2(n) + n - 1 因为 T(1) 是一个常数，所以我们可以将其合并到最后一个常数项中，得到最终结果： T(n) = n * log2(n) + (n - 1) * log2(n) + n - 1 = (n + n - 1) * log2(n) + n - 1 = 2n * log2(n) + n - 1 所以，递归方程 T(n) = 2 * T(n / 2) + (n - 1) 的解为 T(n) = 2n * log2(n) + n - 1。

我昨天面也问了海量数据topk词频

是提前批么

这个左程云快排课上讲过，应该不算让你单算T(n) = 2 * T(n / 2) + (n - 1)，这个是最好情况，但是其他情况也有可能比如T(5N/6)+T(N/6)这些情况求期望就可以得到nlogn，😂他说算法导论上有，你想看可以去看一下，应该挺麻烦的

试试这个

组合数学早忘完了

主定理直接求，可以吗，还是要一步步推

主定理

我超 第三题他就这样问的？