第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全,請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問題,去搜搜看,總會(huì)有你想問的

未排序列表與線性和二分搜索

未排序列表與線性和二分搜索

繁華開滿天機(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ù)更有效。


查看完整回答
反對(duì) 回復(fù) 2021-09-14
?
揚(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ì)增加損失。

如果只需要搜索一次,線性搜索是最好的選擇。


查看完整回答
反對(duì) 回復(fù) 2021-09-14
  • 3 回答
  • 0 關(guān)注
  • 206 瀏覽
慕課專欄
更多

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)