chapter2_answer

一、讨论题1.O(n2n^2n2)2.O(nnn)3.O(log⁡(n)\log (n)log(n))4.O(n3n^3n3)2.O(nnn)二、编程练习1.设计一个实验，证明列表的索引操作为常数阶。2.设计一个实验，证明字典的取值操作和赋值操作为常数阶。3.列表和字典比较del 操作的性能4.给定一个数字列表，其中的数字随机排列，编写一个线性阶算法，找出第k 小的元素,并解释为何该算法的阶是线性的。5.针对前一个练习，能将算法的时间复杂度优化到O(nlognn log nnlogn)吗？三、总结

一、讨论题

1.O(n2n^2n2)

2.O(nnn)

3.O(log⁡(n)\log (n)log(n))

4.O(n3n^3n3)

2.O(nnn)

二、编程练习

1.设计一个实验，证明列表的索引操作为常数阶。

import timeitimport randomimport numpy as npimport matplotlib.pyplot as pltimport pandas as pdlenx = []listy = []color = ['c', 'b', 'g', 'r', 'm', 'y', 'k', 'w']for i in range(10000, 1000001, 20000):t = timeit.Timer("x[random.randrange(%d)]" % i,"from __main__ import random, x")x = list(range(i))list_time = t.timeit(number=1000)print("%d, %10.3f" % (i, list_time))lenx.append(i)listy.append(list_time)ax = plt.gca()# 去掉边框ax.spines['top'].set_color('none')ax.spines['right'].set_color('none')# 移位置 设为原点相交ax.xaxis.set_ticks_position('bottom')ax.spines['bottom'].set_position(('data', 0))ax.yaxis.set_ticks_position('left')ax.spines['left'].set_position(('data', 0))listdot = plt.scatter(lenx, listy, c=color[3], edgecolors='r', label='list')plt.xlabel('lenth(list)')plt.ylabel('time(/s)')plt.title('List_index')plt.legend()plt.show()

2.设计一个实验，证明字典的取值操作和赋值操作为常数阶。

字典取值操作：dict.get(key)

import timeitimport randomimport numpy as npimport matplotlib.pyplot as pltimport pandas as pdlenx = []dicty = []color = ['c', 'b', 'g', 'r', 'm', 'y', 'k', 'w']for i in range(10000, 1000001, 20000):t = timeit.Timer("x.get(random.randrange(%d))" % i, "from __main__ import random, x") x = {j: None for j in range(i)}dict_time = t.timeit(number=1000)print("%d, %10.3f" % (i, dict_time))lenx.append(i)dicty.append(dict_time)ax = plt.gca()# 去掉边框ax.spines['top'].set_color('none')ax.spines['right'].set_color('none')# 移位置 设为原点相交ax.xaxis.set_ticks_position('bottom')ax.spines['bottom'].set_position(('data', 0))ax.yaxis.set_ticks_position('left')ax.spines['left'].set_position(('data', 0))dictdot = plt.scatter(lenx, dicty, c=color[3], edgecolors='r', label='dict')plt.xlabel('lenth(dict)')plt.ylabel('time(/s)')plt.title('dict_assign()')plt.legend()plt.show()

2. 字典赋值操作：dict[key] = value

# t = timeit.Timer("x.get(random.randrange(%d))" % i, "from __main__ import random, x")t = timeit.Timer("x[random.randrange(%d)] = random.randrange(%d)" % (i,i), "from __main__ import random, x")

3.列表和字典比较del 操作的性能

import timeitimport randomimport numpy as npimport matplotlib.pyplot as pltimport pandas as pdlenx = []listy = []dicty = []color = ['c', 'b', 'g', 'r', 'm', 'y', 'k', 'w']for i in range(1000000, 100000001, 1000000):t = timeit.Timer("del x[random.randrange(%d)]" % i, "from __main__ import random, x")x = list(range(i))list_time = t.timeit(number=1)x = {j:None for j in range(i)}dict_time = t.timeit(number=1)print("%d, %15.5f, %15.5f" % (i, list_time, dict_time))lenx.append(i)listy.append(list_time)dicty.append(dict_time)ax = plt.gca()# 去掉边框ax.spines['top'].set_color('none')ax.spines['right'].set_color('none')# 移位置 设为原点相交ax.xaxis.set_ticks_position('bottom')ax.spines['bottom'].set_position(('data', 0))ax.yaxis.set_ticks_position('left')ax.spines['left'].set_position(('data', 0))listdot = plt.scatter(lenx, listy, c=color[3], edgecolors='r', label='list')dictdot = plt.scatter(lenx, dicty, c=color[1], edgecolors='b', marker='^', label='dict')plt.xlabel('lenth(list&dict)')plt.ylabel('time(/s)')plt.title('List&Dict_del_analysis')plt.legend()plt.show()

4.给定一个数字列表，其中的数字随机排列，编写一个线性阶算法，找出第k 小的元素,并解释为何该算法的阶是线性的。

&

5.针对前一个练习，能将算法的时间复杂度优化到O(nlognn log nnlogn)吗？

import timeitimport randomimport numpy as npimport matplotlib.pyplot as pltimport pandas as pddef findkMin(x, k):if k == 0:return -1k -= 1while k:temp = x[0]j = 0for i in range(len(x)):if temp > x[i]:temp = x[i]j = idel x[j]k -= 1temp = x[0]for i in range(len(x)):if temp > x[i]:temp = x[i]return tempdef findkMin1(x, k):# if k == 0:#return -1x.sort()return x[k-1]lenx = []find1y = []find2y = []color = ['c', 'b', 'g', 'r', 'm', 'y', 'k', 'w']if __name__ == '__main__':x1 = [1,3,2,4]x = list(range(100))np.random.shuffle(x)print(x)print(findkMin1(x,0))for i in range(100, 200000, 1000):t1 = timeit.Timer("findkMin(x,random.randrange(%d))" % i, "from __main__ import random, x,findkMin")t2 = timeit.Timer("findkMin1(x,random.randrange(%d))" % i, "from __main__ import random, x,findkMin1")x = list(range(i))np.random.shuffle(x)findtime1 = t1.timeit(number=1)x = list(range(i))np.random.shuffle(x)findtime2 = t2.timeit(number=1)print("%d, %15.6f，%15.6f" % (i, findtime1, findtime2))lenx.append(i)find1y.append(findtime1)find2y.append(findtime2)ax = plt.gca()# 去掉边框ax.spines['top'].set_color('none')ax.spines['right'].set_color('none')# 移位置 设为原点相交ax.xaxis.set_ticks_position('bottom')ax.spines['bottom'].set_position(('data', 0))ax.yaxis.set_ticks_position('left')ax.spines['left'].set_position(('data', 0))plt.scatter(lenx, find1y, c=color[3], edgecolors='r', label='FindKMin1')plt.scatter(lenx, find2y, c=color[1], edgecolors='b', marker='^', label='FindKMin2')plt.xlabel('lenth(list)')plt.ylabel('time(/s)')plt.title('FindKMin_analysis')plt.legend()plt.show()

使用排序方法的**findkmin()**时间复杂度并不是常数，如下：

三、总结

主要学习了

1.大O记法，

2.时间复杂度，

3.python绘制散点图，

4.如何对简单的python程序进行基准测试等。