使用主定理或展开求解
Solve using either master theorem or by expansion
我有两个问题，我一直在尝试但无法弄清楚。
1) () = ( − 1) + ^4
2) () = 2 (/2) + lg
对于第一个，我假设替换（我正确吗？），并得到 kb + T(n-k)。很确定那是错误的，所以需要帮助。
第二个，我完全不知道...
任何帮助都会很棒！谢谢！
1) 所以你得到了
……？我不知道你是怎么得到这个的，但它肯定是不正确的。
这基本上是 n 以内所有整数的 4 次方之和。标准公式是：
2) 将这个继续展开，我们可以找到一个规律：
限制log n - 1是因为我们一直将T的参数除以2，所以上面的替换可以继续log n行，直到T(1)或者停止条件在哪里。继续使用 对数规则（google 如果你不知道的话）：
两个求和都有 log n 项。由于第一个求和根本不依赖于 i，我们简单地乘以 log n。第二次求和由 1（或 0，在这种情况下无关紧要）的整数求和的标准公式给出：
我有两个问题，我一直在尝试但无法弄清楚。 1) () = ( − 1) + ^4 2) () = 2 (/2) + lg
对于第一个，我假设替换（我正确吗？），并得到 kb + T(n-k)。很确定那是错误的，所以需要帮助。
第二个，我完全不知道...
任何帮助都会很棒！谢谢！
1) 所以你得到了
……？我不知道你是怎么得到这个的，但它肯定是不正确的。
这基本上是 n 以内所有整数的 4 次方之和。标准公式是：
2) 将这个继续展开，我们可以找到一个规律：
限制log n - 1是因为我们一直将T的参数除以2，所以上面的替换可以继续log n行，直到T(1)或者停止条件在哪里。继续使用 对数规则（google 如果你不知道的话）：
两个求和都有 log n 项。由于第一个求和根本不依赖于 i，我们简单地乘以 log n。第二次求和由 1（或 0，在这种情况下无关紧要）的整数求和的标准公式给出：