2.Python数据结构与算法分析课后习题__chapter2

chapter2_answer

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

一、讨论题

1.O( n 2 n^2 n 2 )

2.O( n n n )

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

4.O( n 3 n^3 n 3 )

2.O( n n n )

二、编程练习

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

import timeit
import random
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

lenx = []
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.设计一个实验，证明字典的取值操作和赋值操作为常数阶。

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

import timeit
import random
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

lenx = []
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()

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

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

import timeit
import random
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

lenx = []
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( n l o g n n log n n l o g n )吗？

import timeit
import random
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

def findkMin(x, k):
    if k == 0:
        return -1
    k -= 1
    while k:
        temp = x[0]
        j = 0
        for i in range(len(x)):
            if temp > x[i]:
                temp = x[i]
                j = i
        del x[j]
        k -= 1
    temp = x[0]
    for i in range(len(x)):
        if temp > x[i]:
            temp = x[i]
    return temp

def findkMin1(x, k):

    x.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()

三、总结

主要学习了

1.大O记法，
2.时间复杂度，
3.python绘制散点图，
4.如何对简单的python程序进行基准测试等。

Original: https://blog.csdn.net/conan04260426/article/details/127028641
Author: 纳梨
Title: 2.Python数据结构与算法分析课后习题__chapter2