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

catspeake
TA貢獻(xiàn)1111條經(jīng)驗(yàn) 獲得超0個(gè)贊
線性搜索只需要O(n),而對(duì)列表進(jìn)行排序首先需要O(n log n)。由于您將只在列表中搜索一個(gè)值,因此使用二分搜索在排序列表中進(jìn)行后續(xù)搜索僅需要O(log n) 的事實(shí)無助于克服O(n log n)時(shí)間復(fù)雜度的開銷參與排序,因此線性搜索對(duì)任務(wù)更有效。

揚(yáng)帆大魚
TA貢獻(xiàn)1799條經(jīng)驗(yàn) 獲得超9個(gè)贊
對(duì)列表進(jìn)行排序O(log(N)*N)
充其量具有復(fù)雜性。
線性搜索具有O(N)
復(fù)雜性。
因此,如果您必須多次搜索,則在進(jìn)行一些搜索后,您就會(huì)開始獲得時(shí)間。
如果對(duì)象是可散列的(例如:整數(shù)),排序+二分搜索的一個(gè)不錯(cuò)的替代方法(僅搜索多次時(shí))是將它們放在set
. 然后復(fù)雜性歸結(jié)為O(1)
散列,但仍然O(N)
要?jiǎng)?chuàng)建它,而散列會(huì)增加損失。
如果只需要搜索一次,線性搜索是最好的選擇。
添加回答
舉報(bào)
0/150
提交
取消