数据结构学习 - 绪论

算法

● 确定性
    可以描述为一个由基本操作组成的序列
● 可行性
    每一基本操作都可实现，且在常数时间内完成
● 有穷性

大 O 记号

T(n) = O(f(n)) iff 存在 c>0，当 n>>2 时，有 T(n)<c*f(n)

• 常数 : O(1)
  对数 : O(logn)
  多项式 : O(n^c) [ 线性 ]
  指数 : O(a^n) [ 任意 c >1，n^c = O(2^n) ]

级数

• 算数级数：与末项平方同阶
  T(n) = 1 + 2 + 3 + … + n = n(n+1)/2 = O(n^2)

• 幂方级数：比幂次高出一阶
  T2(n) = 1^2 + 2^2 + 3^2 + … + n^2 = n(n+1)(2n+1)/6 = O(n^3)

• 几何级数：与末项同阶
  Ta(n) = a^0 + a^1 + a^2 + a^3 + … + a^n = (a^(n+1) -1)/(a-1) = O(a^n)

• 收敛级数
  和趋向一个常数：O(1)

• 调和级数（log : 通常以 2 为底数）
  h(n) = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n = O(logn)
  log1 + log2 + log3 + ... + logn = log(n!) = O(nlogn)

• Concrete Mathematics（建议阅读书目）
  

  ---

笔记学习于
数据结构(自主模式)-清华大学-邓俊辉
笔记中代码均出自该学习视频

MOOC课程地址：
http://www.xuetangx.com/courses/course-v1:TsinghuaX+30240184+sp/about