本文共 1421 字，大约阅读时间需要 4 分钟。

Introduction to Algorithms算法导论笔记

算法导论Lesson1

课程简介：

内容主要包括：

• 算法的含义、意义的简要介绍；
• 算法的分析；
• 插入排序、合并排序
• 如下图：
  如下图：

preface Analysis of Algorithms The theoretical study of computer program performance and resource usage

What’s more important than perf?

cost, ux Why study algs and perf? infeasable ->feasable perf like the currency in economy Perf is the precondition to have good ux. bottom of heap Speed is always fun.

Problem Sorting

input sequence [a1,a2,…,an] of numbers output permutation[a1’,a2’,…,an’] to sorted as smaller->bigger

Insertion Sort

Running time: - depends on input(e.g. sorted already) - depends on input size( 6 elem. vs 6*10**9)

Kinds of analysis

• Worst-case(usually)

  T(n) =max time on any input of size n

• Average-case:(sometimes)

  T(n)=expected time over all inputs of size n

  (Need assumption of stat. distr.)

• Best-case:(bogus)

  cheat

What’s my sort’s worst time?

Depends on computer

• relative speed(on same machine)

• absolute speed(on different machines)

  BIG DATA
  渐进分析
  look at the growth of time when n->infinity
  Asymptotic notation:

  O(n**3) Drop low-order such as n**2,n,constant and leading constant.

  arithmetic series（算术级数，等差级数）

  教授居然说，我们这里有高手知道算数级数，沟通就好办了。
  Merge Sort

  

  1. If n=1, done
  2. Recursively sort
     a[1,…n/2] and
     a[n/2+1,…n]
  3. Merge 2 sorted lists.
     Key Subroutine: Merge
     20 12
     13 11
     7 9
     2 1
     1 2 7 9 11 13 12 20

小结：

两种排序算法 对于排序问题，本节课提供了两种算法，分别是插入排序和合并排序。

插入排序是O(n*n)，合并排序是O(nlgn)

其中合并排序运用了递归调用和分治策略，这两个内容将分别在后续两节中介绍。

转载地址：http://jojtb.baihongyu.com/