第一章 基础知识

什么是算法？

算法就是定义任何良性的计算过程，该过程区某个值或者值的集合作为输入并产生某个值或值集合作为输出。

为什么算法指的研究？

有效的算法可以解决很多实际问题

算法的作用？

提个效率，节约成本，书中举了最短运输路径的例子

算法基础

插入排序

题目：输入n个数的一个序列<a1,a2,....an>
输出一个序列<a1‘，a2',.....an'>, 满足a1'<a2',...<an'

书中举了一个 扑克牌插入的例子，非常生动。
总结下：就是每次在排好序的序列从右到左，找到插入位置

insertion-sort(A)
for i=1-> A.length
      key = A[i]
      //把key 插入到A[0,i-1]的有序序列里面
      j = i-1
     while (j >0 & key < A[j])
              A[j+1] = A[j]
              j=j-1
    A[j+1]=key

分析算法

最坏情况&平均情况

设计算法

分治法（归并排序）

image.png image.png

merge-sort(A,p,r)
  if p < r
     q = (p+r)/2
     merge-sort(A,p,q)
     merge-sort(A,q+1,r)
     merge(A,p,q,r)

merge(A,p,q,r)
  n1 = q-p+1
  n2 = r-q
  let L[1,n1+1] ,R[1,n2+1] empty array
  for i = 1 to n1
       L[i] = A[q+i-1]
  for i = 1 to n2
      R[i] = A[q+i]
   
  L[n1+1] = &
  R[n2+1] = &
   i = 1, j = 1
  for  k = p to r
       if L[i]<R[j]
       A[k] = L[i]
       i++
      else 
       A[key] = R[j]
       j++

递归树

image.png