数据结构与算法-基础概念

2020-01-09 181 阅读1分钟

算法： 用于解决特定问题的一系列的执行步骤
如何评判一个算法的好坏
- 正确性、可读性、健壮性(对不合理输入的反应能力和处理能力)
- 时间复杂度(time complexity):估算程序指令的执行次数(执行时间)
- 空间复杂度(space complexity):估算所需占用的存储空间
大O表示法

一般用大O表示法来描述复杂度，它表示的是数据规模 n 对应的复杂度

大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率
- 忽略常数、系数、低阶
  
  $9 >> O(1)$
  
  $2n + 3 >> O(n)$
  
  $n^2 + 2n + 6 >> O(n^2)$
  
  $4n^3 + 3n^2 + 22n + 100 >> O(n^3)$
- 对数阶一般省略底数，
$\log_2n = \log_29 * \log_9n$

所以

$\log_2n 、\log_9n$

统称为

$\log{n}$
常见的复杂度