首頁(yè) 猿問(wèn) 時(shí)間復(fù)雜度為什么是O(nlgn)

時(shí)間復(fù)雜度為什么是O(nlgn)

JavaScript

四季花海 2019-03-30 09:29:22

O(lgn)的解釋是:將一個(gè)數(shù)據(jù)集分成兩半,然后將分開的每一半再分成兩半,依此類推O(nlgn)的解釋是:將一個(gè)數(shù)據(jù)集分成兩半,然后將分開的每一半再分成兩半,依此類推,在此過(guò)程中同時(shí)遍歷每一半數(shù)據(jù)O(lgn)我可以理解,但我不理解為什么在此過(guò)程中同時(shí)遍歷每一半數(shù)據(jù)就得乘以n,這個(gè)n怎么算出來(lái)的?誰(shuí)能舉個(gè)簡(jiǎn)單又實(shí)際的例子?

查看完整描述

2 回答

猛跑小豬

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

以快速排序?yàn)槔趇輪中，數(shù)據(jù)集已被分為2^(i-1)塊，在選定這么多個(gè)pivot之后，要遍歷所有n個(gè)元素才能把所有2^(i-1)個(gè)塊分為2^i塊，這個(gè)過(guò)程一共要做log(n)次，可不就是n*log(n)？

反對(duì) 回復(fù) 2019-03-30

胡子哥哥

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

把n的問(wèn)題看成一棵二叉樹。logN算法就是從root找到一個(gè)葉子結(jié)點(diǎn)，復(fù)雜度為樹高，也就是logN。NlogN算法則是從root找到每一個(gè)葉子結(jié)點(diǎn)，復(fù)雜度為樹高*葉子結(jié)點(diǎn)個(gè)數(shù)，也就是logN*N建議找本書看嚴(yán)格的證明

反對(duì) 回復(fù) 2019-03-30