算法导论的一道思考题

1.2-2 假设我们正在比较插入排序和并归排序在相同机器上的实现。对规模n的输入，插入排序程序运行8n^2步，而并归排序运行64nlogn步，对于哪些n值，插入排序优于并归排序？

首先我们都知道
插入排序的时间复杂度为n^2，也就是我们常说比较高的时间复杂度，实际应用需要试验结果得出
并归排序的时间复杂度为nlogn，同比之下，并归速度吊打插入，肯定用并归做算法！

书中给到一个例子，让一个超级大牛写插入排序，只要8次就能运行完整个插入排序
一个菜鸟写并归，他需要写64次代码才能执行完，于是需要我们做一个对比，真的无论什么时候都需要选择时间复杂度较低算法吗？

插入排序

# 插入排序
def insertion_sort(array):
    for i in range(len(array)):
        cur_index = i
        while array[cur_index - 1] > array[cur_index] and cur_index - 1 >= 0:
            array[cur_index], array[cur_index - 1] = array[cur_index - 1], array[cur_index]
            cur_index -= 1
    return array

并归排序

# 切割数组 的函数
def merge_sort(alist):
    # 如果长度小于等于1 ，不能再分割了
    if len(alist) <= 1:
        return alist

    # 根据列表长度确定拆分的中间位置
    mid_index = len(alist) // 2

    # 递归调用，无限切割下去
    left_list = merge_sort(alist[:mid_index])
    right_list = merge_sort(alist[mid_index:])
    return merge(left_list, right_list)


# 排序的函数
def merge(left_list, right_list):
    l_index, r_index = 0, 0
    merge_list = []
    # 判断列表里面是否还有元素可以用
    while l_index < len(left_list) and r_index < len(right_list):
        # 哪边的元素小于另外一边的的元素就把哪边的元素加入进去，对应的索引加一
        if left_list[l_index] < right_list[r_index]:
            merge_list.append(left_list[l_index])
            l_index += 1
        else:
            merge_list.append(right_list[r_index])
            r_index += 1
    # 下面的这两个就是，如果有一个列表全部添加了，另外一个列表直接添加到merge_list里面了
    merge_list += left_list[l_index:]
    merge_list += right_list[r_index:]
    return merge_list

运行实例

"""
    # 插入排序的时间时间复杂度是n^2
    # 并归排序的时间复杂度为nlg（n）
    什么情况下插入排序比并归排序快?
    前提是规定
        插入排序运行8n^2
        并归排序64nlg(n)
"""
import random

from time import *


def insertion_sort(array):
    for i in range(len(array)):
        cur_index = i
        while array[cur_index - 1] > array[cur_index] and cur_index - 1 >= 0:
            array[cur_index], array[cur_index - 1] = array[cur_index - 1], array[cur_index]
            cur_index -= 1
    return array


"""
Merge_Sort 归并排序
分治算法Divide and Conquer
时间复杂度：
"""


# 切割数组 的函数
def merge_sort(alist):
    # 如果长度小于等于1 ，不能再分割了
    if len(alist) <= 1:
        return alist

    # 根据列表长度确定拆分的中间位置
    mid_index = len(alist) // 2

    # 递归调用，无限切割下去
    left_list = merge_sort(alist[:mid_index])
    right_list = merge_sort(alist[mid_index:])
    return merge(left_list, right_list)


# 排序的函数
def merge(left_list, right_list):
    l_index, r_index = 0, 0
    merge_list = []
    # 判断列表里面是否还有元素可以用
    while l_index < len(left_list) and r_index < len(right_list):
        # 哪边的元素小于另外一边的的元素就把哪边的元素加入进去，对应的索引加一
        if left_list[l_index] < right_list[r_index]:
            merge_list.append(left_list[l_index])
            l_index += 1
        else:
            merge_list.append(right_list[r_index])
            r_index += 1
    # 下面的这两个就是，如果有一个列表全部添加了，另外一个列表直接添加到merge_list里面了
    merge_list += left_list[l_index:]
    merge_list += right_list[r_index:]
    return merge_list


if __name__ == '__main__':
    N = 2000
    alist = [random.randint(1, 1000) for i in range(N)]
    begin_time = time()
    for i in range(8):  # 这里代表8次
        insertion_sort(alist)
    end_time = time()
    run_time = end_time - begin_time
    print("这是插入排序，时间复杂度为8n^2的排序{}个元素运行的时间:{}".format(N, run_time))

    begin_time = time()
    # print('原列表的顺序{}'.format(alist))
    for i in range(64):  # 这里代表8次
        alist = merge_sort(alist)
    end_time = time()
    run_time = end_time - begin_time
    print('这是并归排序，时间复杂度为64nlg(n)的排序{}个元素所运行的时间：{}'.format(N, run_time))

n等于1000的运行结果，明显时间复杂度较高的插入排序速度明显快于并归

实验数据：排序1000个元素
插入排序用时 0.114s
并归排序用时 0.237s

n等于1500的运行结果，明显时间复杂度较高的插入排序快于并归

实验数据：排序1500个元素
插入排序用时 0.250s
并归排序用时 0.405s

n等于2000的运行结果，插入排序还是略快于并归，但是已经开始接近了

实验数据：排序2000个元素
插入排序用时 0.468s
并归排序用时 0.570s

n等于2500的运行结果，这是我找到的一个近似于等于值

实验数据：排序2500个元素
插入排序用时 0.708s
并归排序用时 0.709s

n等于3000的运行结果，插入排序速度上开始变慢，但是不太明显

实验数据：排序3000个元素
插入排序用时 1.039s
并归排序用时 0.815s

n等于10000的运行结果，插入排序的速度上明显开始变慢

实验数据：排序10000个元素
插入排序用时 11.194s
并归排序用时 3.187s

结论也是自己的愚见

无论是大牛还是菜鸟，对于合理数值的算法的作用几乎为0，
就算运行8次的插入排序和64次的并归排序也，到达一定峰值的时候，算法的原有性质是没办法改变的
可以看出，在数据量大的时候我们可以选择并归排序，速度无疑是极快的，
但是在某个较小的N值内，明显看到插入排序是可取的

这就是算法的魅力吧，继续记录，继续学习，共勉！