首頁(yè) 猿問(wèn) 未排序列表與線(xiàn)性和二分搜索

未排序列表與線(xiàn)性和二分搜索

Python

繁華開(kāi)滿(mǎn)天機(jī) 2021-09-14 21:35:09

大家好，我一直在為即將到來(lái)的考試而學(xué)習(xí)，我遇到了這個(gè)問(wèn)題：如果您有一個(gè)包含 100 萬(wàn)個(gè)唯一項(xiàng)的未排序列表，并且知道您只會(huì)為一個(gè)值搜索它一次，那么以下哪種算法最快？在未排序列表上使用線(xiàn)性搜索使用插入排序?qū)α斜磉M(jìn)行排序，然后對(duì)排序后的列表進(jìn)行二分查找第二個(gè)選擇不是最快的嗎？排序列表然后查找值而不是僅使用線(xiàn)性搜索？

查看完整描述

3 回答

catspeake

TA貢獻(xiàn)1111條經(jīng)驗(yàn) 獲得超0個(gè)贊

線(xiàn)性搜索只需要O(n)，而對(duì)列表進(jìn)行排序首先需要O(n log n)。由于您將只在列表中搜索一個(gè)值，因此使用二分搜索在排序列表中進(jìn)行后續(xù)搜索僅需要O(log n) 的事實(shí)無(wú)助于克服O(n log n)時(shí)間復(fù)雜度的開(kāi)銷(xiāo)參與排序，因此線(xiàn)性搜索對(duì)任務(wù)更有效。