分类目录归档:Algorithm

MIT CLRS open courese-1/23

  1. Insertion-sort Algorithm 插入排序
  2. Running time:upper bounds)时间消耗~ input, problem size.
    • worse case
    • average case(weighted average in assumption situation)
    • best case(bogus)
  3. 渐进分析:Asymptotic notation渐进符号 theta: 舍去低阶项,忽略常数项。
  4. 累加求和:arithmetic series算术级数。1+2+3+…+n=θ(n^2)

 

  1. merge sort after recursively sort 归并排序
    • 输入是分为两半
    • 观察两个输入序列最小的元素,提出放tmp,并在原始输入序列删除;
    • 再次在两个输入序列开头寻找最小元素
    • loop
  2. 时间消耗 linear time线性时间 order n:O(n).
    • 只关注两个序列最头上的两个,不管输入序列大小。
    • recursion tree递归树 θ(nlgn)
    • θ(nlgn)>θ(n^2)asymptotically。
  3. 归并排序θ(nlgn)在充分大的输入规模下,将快于插入排序θ(n^2)。