MIT算法导论1–课程简介及算法分析

Posted bymyyzwPosted inalgorithmsTags:, ,

resource：算法导论
website:https://www.bilibili.com/video/av48922404?p=1

Analysis of algorithms

The theoretical of computer-program performance and resource usage

  • What’s more important than performance?
  • Why study algorithms and performance?

Problem sorting:

Input: seaquence <a1,a2,a3…an> if numbers
output: permutation<b1,b2,b3…bn>
such that b1<b2<b3<…<bn

Insertion sort

insertion.Sort(Ain)//Sorts A[1…n]

for j<- 2 to n
    do key<-A[j]
        i<-j-1
        while i>0 and A[i]>key
            do A[i+1]<-A[i]
                i<-i-1
        A[i+1]<-key

EX: A=
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
2 3 4 6 8 9 Done

Running time:

  • depends on input(eg: already sorted)
  • depends on input size(eg: 6 elem vs 6*10^9)
    • parameterize in input size
  • Want upper bounds
    • guarantee to user

Kinds of analysis

  • worst case(usually)
    • T(n)=max time on any input of size(relation not function)
  • Average case(sometimes)
    • T(n)= expected time over all input of size
    • Need assumption of stat. distribution
  • Best case(bogus)
    • Cheat

What is insertion sort’s worst time?

  • Depends on computer
    • relative speed(on some machine)
    • absolute speed(on diff machine)
  • Big Idea! asymptotic analysis 渐近分析
    • Ignore machine dependent constants
    • Look at growth of T(n) as n->∞

Asymptotic notation

  • Θ-notation
    • Drop low order terms
    • Ignore leading constants EX: 3n^3 +90n^2-5n+345=Θ(n^3)
      As n->∞，Θ(n^2) alg always best beats Θ(n^3) alg

Insertion sort analysis

  • Worst case reverse Sorted
    • Θ(n)=∑(j=2->n)Θ(j)=Θ(n^2)

Is insertion sort fast?

  • Moderately so for small n
  • Not at all for large n

Merge Sort

Merge Sort A[1…n] T(n)

  1. If n=1,done Θ(1)
  2. Recursively sort 2TΘ(n/2) A[1 [n/2]] and A[[n/2]+1,n]
  3. Merge 2 sorted lists Θ(n)

Key subroutine(子程序) Merge

20 12 7 2
13 11 9 1
Time=Θ(n) on n total elments

Recursive

T(n)=Θ(1) if n=1 (usually omit)
T(n)=2TΘ(n/2)+Θ(n) if n>1
Recursion tree T(n)=2T(n/2)+cn, const>0

What is Height of the tree?lgn
how many leave does this tree have?n

T(n)=   cn      =              cn                --cn
   T(n/2) T(n/2)       T(n/2)      T(n/2)        --cn
                  T(n/2) T(n/2)   T(n/2) T(n/2)  --cn
                  ...
                  Θ(1)                           --Θ(n)
                                         total: cnlgn+Θ(n)=Θ(nlgn)

Insertion sort:

def insert_sorted_num(nums, num):
    if not nums:
        return [num]

    if nums[-1] < num:
        return nums + [num]

    if num<nums[0]:
        return [num]+nums

    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] > num:
            r = mid - 1
        else:
            l = mid + 1
    return nums[:r+1] + [num] + nums[r+1:]


def insertion_sort(nums):
    rep = []
    for num in nums:
        rep = insert_sorted_num(rep, num)
    return rep

Merge Sort

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    k = len(nums) // 2
    return merge_two_sorted_list(merge_sort(nums[:k]), merge_sort(nums[k:]))


def merge_two_sorted_list(nums1, nums2):
    nums = []
    i, j = 0, 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            nums.append(nums1[i])
            i += 1
        else:
            nums.append(nums2[j])
            j += 1
    if i != len(nums1):
        nums += nums1[i:]
    if j != len(nums2):
        nums += nums2[j:]
    return nums

Leave a comment