数据结构与算法分析

Chapter 2 算法分析
2-1 计算前n个整数之和

def sumOFN(n):
    theSum = 0
    for i in range(1,n+1):
        theSum = theSum + i
        
    return theSum

2-3 计算执行时间

import time

def sumOFN2(n):
    start = time.time()
    
    theSum = 0
    for i in range(1,n+1):
        theSum = theSum + i
        
    end = time.time()
    
    return theSum,end-start        
      for i in range(5):
        print("Sum is %d required %10.7f seconds" % sumOFN2(100000))  

2-4 不使用循环来计算前n个整数的和

def sumOFN3(n):
    return (n * (n+1))/2

import time

def sumOFN3(n):
    start = time.time()
    
    theSum = (n * (n+1))/2
    return theSum
        
    end = time.time()
    
    return theSum,end-start

lee = sumOFN3(10000)
print(lee)

2-6 实现清点方案

def anagramSolution1(s1,s2):
    alist = list(s2)
    pos1 = 0
    stillOK = True
    
    while pos1 < len(s1) and stillOK:
        pos2 = 0
        found = False
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = Ture
            else:pos2 = pos2 + 1
                
                
        if found:
            alist[pos2] = None
        else:
            stillOK = False
        
    pos1 = pos1 + 1
    
    return stillOK

s1 = [1,2,3,4]
s2 = [5,6,7,8]
lee1 = anagramSolution1(s1,s2)
print(lee1)       

2-7 实现排序方案

def anagramSolution2(s1,s2):
    
    alist1 = list(s1)
    alist2 = list(s2)
    
    alist1.sort()
    alist2.sort()
    
    pos = 0
    matches = True
    
    while pos < len(s1) and matches:
        if alist1[pos] == alist2[pos]:
            pos = pos + 1
        else:
            matches = False
            
    return matches

s1 = [1,2,3,4]
s2 = [1,2,3,4]
lee1 = anagramSolution2(s1,s2)
print(lee1)

2-8 实现计数方案

def anagramSolution4(s1,s2):
    c1 = [0] * 26
    c2 = [0] * 26
    
    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')
        c1[pos] = c1[pos] + 1
        
    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] = c2[pos] + 1
    
    j = 0
    stillOK = True
    while j < 26 and stillOK:
        if c1[j] == c2[j]:
            j = j+1
        else:
            stillOK = False
            
    return stillOK

s1 = ['a','b','c','d']
s2 = ['a','b','c','f']
lee4 = anagramSolution4(s1,s2)
print(lee4)  

2-9 生成列表的4种方式

def test1():
    l = []
    for i in range(1000):
        l = l + [i]
        
        
def test2():
    l = []
    for i in range(1000):
        l.append(i)
        
        
def test3():
    l = [i for i in range(1000)]
    
    
def test4():
    l = list(range(1000))

from timeit import Timer
t1 = Timer("test1()","from __main__ import test1")
print("concat",t1.timeit(number = 1000),"milliseconds")

t2 = Timer("test2()","from __main__ import test2")
print("append",t2.timeit(number = 1000),"milliseconds")

t3 = Timer("test3()","from __main__ import test3")
print("comprehension",t3.timeit(number = 1000),"milliseconds")

t4 = Timer("test4()","from __main__ import test4")
print("list range",t4.timeit(number = 1000),"milliseconds")      

2-10 pop的性能分析

import  timeit
popzero = timeit.Timer("x.pop(0)", "from __main__ import x")
popend = timeit.Timer("x.pop()", "from __main__ import x")

x = list(range(2000000))
popzero.timeit(number = 1000)

x = list(range(2000000))
popend.timeit(number = 1000)

2-11 比较pop(0)和pop()在不同列表长度下的性能

import  timeit
popzero = timeit.Timer("x.pop(0)", "from __main__ import x")
popend = timeit.Timer("x.pop()", "from __main__ import x")
print("pop(0) pop()")
for i in range(1000000,100000001,1000000):
    x = list(range(i))
    pt = popend.timeit(number = 1000)
    x = list(range(i))
    pz = popzero.timeit(number = 1000)
    print("%15.5f, %15.5f" % (pz,pt))

2-12 比较列表和字典的包含操作

import timeit 
import random

for i in range(10000,1000001,20000):
    t = timeit.Timer("random.randrange(%d) in x" % i,
                    "from __main__ import random, x")
    x = list(range(i))
    lst_time = t.timeit(number = 10000)
    x = {j:None for j in range(i)}
    d_time = t.timeit(number = 10000)
    print("%d, %10.3f, %10.3f" % (i, lst_time, d_time))