leetcode

时间复杂度 & 空间复杂度

评估一个算法的性能有两个指标：执行事件、内存消耗。
通常服务端更关注执行时间，因为内存消耗可以回收，而且用户也不care你服务器端到底占用了多大空间。
leetcode采用的是事后评估法，采用更多的是事前评估 - 大O复杂度表示法，也就引出了两个概念：

• (渐进)时间复杂度
• (渐进)空间复杂度
• 渐进：当输入规模成倍数增加的时候，相应的时间空间消耗增加了多少
• 时间复杂度和空间复杂度通常不能同时最优，不是有种说法：时间换取空间、空间换取时间，一般选后种，毕竟空间是可以回收的、也可以用钱买么
  e.g.
• 从1依次加到100 VS 从1依次加到10000
• 高斯算法 (1+100)*100/2 V$ (1+10000)*10000/2

二分查找 - 减而治之

• e.g.
  • [猜数字]
  • [查字典]
  • [debug打印输出语句]
• 应用：
  • 有序数组中查找一个数 - 二分下标
  • 整数范围内查找一个整数 - 二分答案
  • (有序数组 也可以是旋转数组或山脉数组，都是有规律可循的，都可以用二分查找)