我需要一些关于python代码的帮助。在
我做了两个函数,一个用于顺序(线性)搜索,另一个用于二进制搜索。在
我想对给定列表中的每个大小值执行以下3项操作:
1)生成给定列表大小的随机整数值列表(介于1到10000000之间)
2)对列表中的-1运行顺序搜索,并记录顺序搜索所用的时间
3)在排序后的列表上运行-1的二进制搜索(在对列表排序后),并记录二进制搜索所用的时间
我所做的是:
def sequentialSearch(alist, item):
pos = 0
found = False
while pos < len(alist) and not found:
if alist[pos] == item:
found = True
else:
pos = pos + 1
return found
def binSearch(list, target):
list.sort()
return binSearchHelper(list, target, 0, len(list) - 1)
def binSearchHelper(list, target, left, right):
if left > right:
return False
middle = (left + right)//2
if list[middle] == target:
return True
elif list[middle] > target:
return binSearchHelper(list, target, left, middle - 1)
else:
return binSearchHelper(list, target, middle + 1, right)
import random
import time
list_sizes = [10,100,1000,10000,100000,1000000]
for size in list_sizes:
list = []
for x in range(size):
list.append(random.randint(1,10000000))
sequential_search_start_time = time.time()
sequentialSearch(list,-1)
sequential_search_end_time = time.time()
print("Time taken by linear search is = ",(sequential_search_end_time-sequential_search_start_time))
binary_search_start_time = time.time()
binSearch(list,-1)
binary_search_end_time = time.time()
print("Time taken by binary search is = ",(binary_search_end_time-binary_search_start_time))
print("\n")
我得到的输出是:
我们知道二进制搜索比线性搜索快得多。 所以,我只想知道为什么二元搜索所花费的时间比线性搜索要多?在
1)您需要说明分拣时间。二进制搜索只对已排序的列表起作用,因此排序需要时间,这就需要时间复杂性来
O(nlogn)
。在你的例子中,你是在计时器开始后排序的,所以它会更高。在2)您正在搜索列表中不存在的元素,即
-1
,这不是二进制搜索的平均情况。二元搜索最糟糕的情况就是要跳转很多次才找不到元素。在3)请不要使用
list
作为变量,它是python的关键字,而且您显然在重写它。用别的东西。在现在,如果你不定时地对列表进行排序。结果变化很大。这是我的。在
我所做的只是在时间安排之前把名单整理一下。太好了,比你一次把它分类和搜索要好得多。在
相关问题 更多 >
编程相关推荐