n個(gè)數(shù)排序算法時(shí)間復(fù)雜度是多少？一般程序員會(huì)脫口而出：O(n!)。這是按照數(shù)學(xué)家的想法，從小到大，或者從大到小，一一比較得到的算法。如果你是一位計(jì)算機(jī)專家，不是一般的程序員，就可以用O(n)時(shí)間復(fù)雜度得出結(jié)果。不信？
我要介紹的方法，不僅可以快速排序，而且可以去掉重復(fù)的數(shù)。
計(jì)算機(jī)專家要你準(zhǔn)備一塊足夠大的干凈存儲(chǔ)空間（一般的計(jì)算機(jī)都可以滿足）。計(jì)算機(jī)專家排序的秘訣就是“將數(shù)放到這個(gè)數(shù)所標(biāo)志的地址單元”！
實(shí)際上，計(jì)算機(jī)內(nèi)部并沒有一般的實(shí)數(shù)，只有無(wú)符號(hào)的二進(jìn)制整數(shù)（更多的請(qǐng)看本人寫的《自己設(shè)計(jì)制作CPU與單片機(jī)》第10章），因而你可以將一個(gè)數(shù)放在這個(gè)數(shù)標(biāo)志的存儲(chǔ)地點(diǎn)（用指針實(shí)現(xiàn)），于是n個(gè)數(shù)排序算法時(shí)間復(fù)雜度就從O(n!)轉(zhuǎn)化成O(n)啦。不僅如此，那些重復(fù)的數(shù)也會(huì)剩下唯一的一個(gè)了。（姜詠江）
快速排序去重？計(jì)算機(jī)專家與程序員的不同 |
|
收藏
分享
支持
反對(duì)
提升卡
置頂卡
沉默卡
喧囂卡
變色卡
千斤頂
照妖鏡
