[作业整理] Python 检测两种查找算法时间复杂度
  • 2017年11月28日
  • 技术类
  • 0评论
  • 227汉字
  • 702围观

前言

这其实是我CS Lab的一个趣味作业。
给定一个只包含数字的数组,求数组中两个数字,要求他们之前的差值最小。花了10分钟写完后,没事干,就整理下记录到博客里。

(其实用了Python == 不考虑效率 23333

两种思路

算法1

用一个嵌套循环,将数组中每两个元素进行减法运算,然后用一个 Tuple 类型储存距离最小的两个数字以及他们的距离。最后 Return。

该算法时间复杂度为:N^N

def closest1(mylist):
    '''
    >>> closest1([15.1, -12.1, 5.4, 11.8, 17.4, 4.3, 6.9])
    (5.4, 4.3)
    >>> closest1([15.1, -12.1, 5.4, 11.8, 17.4, 4.3, 4.3])
    (4.3, 4.3)
    >>> closest1([15.1, -12.1, -12.2, 11.8, 17.4, 4.3, 6.9])
    (-12.1, -12.2)
    '''

    distance = (mylist[0], mylist[1], abs(mylist[0] - mylist[1]))
    for i in range(len(mylist)):
        for j in range(len(mylist)):
            if i != j:
                if abs(mylist[i] - mylist[j]) < distance[2]:
                    distance = (mylist[i],mylist[j],abs(mylist[i]-mylist[j]))

    return (distance[0], distance[1])

算法2

先把数组Sort一遍,用一个For循环,每次比较第i项数字与第i+1项的数字的距离 和 临时最小值Tuple 里面的数值。然后根据条件进行交换算法。
该算法时间复杂度:O(NlogN)+N

def closest2(mylist):
    '''
    >>> closest2([15.1, -12.1, 5.4, 11.8, 17.4, 4.3, 6.9])
    (4.3, 5.4)
    >>> closest1([15.1, -12.1, 5.4, 11.8, 17.4, 4.3, 4.3])
    (4.3, 4.3)
    >>> closest1([15.1, -12.1, -12.2, 11.8, 17.4, 4.3, 6.9])
    (-12.1, -12.2)
    '''
    sorted_list=sorted(mylist)
    distance = (sorted_list[0], sorted_list[1], abs(sorted_list[0] - sorted_list[1]))
    for i in range(len(sorted_list)-1):
        if abs(sorted_list[i]-sorted_list[i+1]) < distance[2]:
            distance = (sorted_list[i], sorted_list[i+1], abs(sorted_list[i] - sorted_list[i+1]))

    return (distance[0],distance[1])

验证

目测是第二种算法的时间复杂度较低,当数组庞大时。完整代码:

import random
import time

def closest1(mylist):
    '''
    >>> closest1([15.1, -12.1, 5.4, 11.8, 17.4, 4.3, 6.9])
    (5.4, 4.3)
    >>> closest1([15.1, -12.1, 5.4, 11.8, 17.4, 4.3, 4.3])
    (4.3, 4.3)
    >>> closest1([15.1, -12.1, -12.2, 11.8, 17.4, 4.3, 6.9])
    (-12.1, -12.2)
    '''

    if len(mylist)<2:
        return (None,None)

    distance = (mylist[0], mylist[1], abs(mylist[0] - mylist[1]))
    for i in range(len(mylist)):
        for j in range(len(mylist)):
            if i != j:
                if abs(mylist[i] - mylist[j]) < distance[2]:
                    distance = (mylist[i],mylist[j],abs(mylist[i]-mylist[j]))

    return (distance[0], distance[1])

def closest2(mylist):
    '''
    >>> closest2([15.1, -12.1, 5.4, 11.8, 17.4, 4.3, 6.9])
    (4.3, 5.4)
    >>> closest1([15.1, -12.1, 5.4, 11.8, 17.4, 4.3, 4.3])
    (4.3, 4.3)
    >>> closest1([15.1, -12.1, -12.2, 11.8, 17.4, 4.3, 6.9])
    (-12.1, -12.2)
    '''
    sorted_list=sorted(mylist)
    distance = (sorted_list[0], sorted_list[1], abs(sorted_list[0] - sorted_list[1]))
    for i in range(len(sorted_list)-1):
        if abs(sorted_list[i]-sorted_list[i+1]) < distance[2]:
            distance = (sorted_list[i], sorted_list[i+1], abs(sorted_list[i] - sorted_list[i+1]))

    return (distance[0],distance[1])


if __name__ == '__main__':
    mylist=[]
    for i in range(10000):
        mylist.append(random.uniform(0.0,1000.0))

    start_time=time.time()
    (x,y)=closest1(mylist)
    spend_time = (time.time() - start_time)
    print("Closet1 Spend Time:",round(spend_time,3),"Result:",x,y)

    start_time=time.time()
    (x,y)=closest2(mylist)
    spend_time = (time.time() - start_time)
    print("Closet2 Spend Time:",round(spend_time,3),"Result:",x,y)

0 评论

近期评论
分类目录
二维码
标签云
赞助二维码

支付宝

微信支付

评论表情