复杂度分析与大 O
n 翻倍耗时到底变几倍、二分在 100 万元素上只要 20 次比较、vector 扩容的 131071 次搬移怎么摊成 1.31、同样 O(n²) 的两种写法差 13 倍——用数字代替直觉。
共 3 篇 · 全部标签
n 翻倍耗时到底变几倍、二分在 100 万元素上只要 20 次比较、vector 扩容的 131071 次搬移怎么摊成 1.31、同样 O(n²) 的两种写法差 13 倍——用数字代替直觉。
斐波那契 n=40 朴素递归 196.9ms vs 迭代 0.0001ms；背包一维滚动写成正序时，有 23% 的随机用例结果"碰巧正确"；二维降到滚动数组是 62.5MB 变 31KB。
500 万元素实测：基数排序 58.9ms 完胜 std::sort 的 329ms，三路快排在全部相等时只要 4.2ms；稳定性测试本身也容易做错——把下标当第二键会让快排"看起来稳定"。