标题党。只是想把人骗进来,因为我不想让有些人看了上一篇帖子没看这篇。
前文: 主定理狗都不学
这里想说一下这个技巧的实际运用注意事项。
正确的复杂度代入递归式可以满足这个技巧,但是错误的复杂度代入递归式也可能满足。
所以做选择题的时候,还是谨慎一点,能用主定理就用,用完可以拿这个检查,不会主定理把所有选项都代进去,然后有多个符合就选最像的那个。
最终代入结果里,要存在正数 k 使得左右最高次项相同且系数相同。