快捷導(dǎo)航

歸并排序時(shí)間復(fù)雜度過(guò)程推導(dǎo)詳解

更新時(shí)間：2021年08月11日 10:53:29 作者：lllllLiangjia

這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)排序算法之歸并排序,對(duì)歸并排序的原理及實(shí)現(xiàn)過(guò)程做了非常詳細(xì)的解讀,需要的朋友可以參考下，希望能幫助到你

歸并排序

歸并排序方法就是把一組n個(gè)數(shù)的序列，折半分為兩個(gè)序列，然后再將這兩個(gè)序列再分，一直分下去，直到分為n個(gè)長(zhǎng)度為1的序列。然后兩兩按大小歸并。如此反復(fù)，直到最后形成包含n個(gè)數(shù)的一個(gè)數(shù)組。

歸并排序總時(shí)間=分解時(shí)間+子序列排好序時(shí)間+合并時(shí)間

無(wú)論每個(gè)序列有多少數(shù)都是折中分解，所以分解時(shí)間是個(gè)常數(shù)，可以忽略不計(jì)。

則：歸并排序總時(shí)間=子序列排好序時(shí)間+合并時(shí)間

如果假設(shè)一個(gè)序列有n個(gè)數(shù)的排序時(shí)間為T(n)，T(n)是一個(gè)關(guān)于n的函數(shù)，隨著n的變化而變化。

那么我們將n個(gè)數(shù)的序列，分為兩個(gè)(n/2)的序列。

那么T(n)=2*T(n/2)+合并時(shí)間

由于合并時(shí)，兩個(gè)子序列已經(jīng)組內(nèi)排好序了，那我們將兩個(gè)排好序的序列組合成一個(gè)大的有序序列，只需要一個(gè)if循環(huán)即可。if循環(huán)中有n個(gè)數(shù)需要比較，所以時(shí)間復(fù)雜度為n。

那么T(n)=2*T(n/2)+n

我們?cè)賹蓚€(gè)n/2個(gè)序列再分成4個(gè)(n/4)的序列。

一個(gè)（n/2）序列排序時(shí)間=兩個(gè)(n/4)的序列排序時(shí)間+兩個(gè)(n/4)的序列的合并為一個(gè)（n/2）的序列時(shí)間

T(n/2)=2*T(n/4)+n/2

將T(n/2)帶入到T(n)中，T(n)=2*(2*T(n/4)+n/2)+n，

通過(guò)化簡(jiǎn)T(n)=4*T(n/4)+2n

我們?cè)賹?個(gè)n/4個(gè)序列再分成8個(gè)(n/8)的序列。

T(n/4)=2*T(n/8)+n/4

將T(n/4)帶入到黃色公式中，T(n)=4*(2*T(n/8)+n/4)+2n

通過(guò)化簡(jiǎn)T(n)=8*T(n/8)+3n

這樣分下去，前面我們已經(jīng)說(shuō)過(guò)了，分為n個(gè)序列，每個(gè)序列里只有一個(gè)數(shù)為止。

前面我們假設(shè)的一個(gè)序列有n個(gè)數(shù)的排序時(shí)間為T(n)，現(xiàn)在每個(gè)序列只有一個(gè)數(shù)，所以不需要進(jìn)行組內(nèi)排序，時(shí)間復(fù)雜度為0。T(1)=0

大家有沒(méi)有找到規(guī)律，右邊式子中n前面的系數(shù)隨著層數(shù)的增加而增加，第一層公式中沒(méi)有n，則系數(shù)為0，第二層n的系數(shù)為1，第三層為2，第四層為3。那么規(guī)律就出來(lái)了，n前面的系數(shù)為層數(shù)減1。

那這個(gè)圖有沒(méi)有很熟悉，就像一個(gè)二叉樹一樣，通過(guò)二叉樹的知識(shí)點(diǎn)我們可以知道，一個(gè)n個(gè)結(jié)點(diǎn)的完全二叉樹層數(shù)為(log2n)+1。

那么n前面的系數(shù)為層數(shù)減1。

(log2n)+1-1=log2n

那log2n就是最底層n的系數(shù)。

那么我們最后一層是不是可以這樣表示

T(n)=n*T(1)+(log2n)*n

T(1)=0，那么T(n)=(log2n)*n

所以歸并排序的時(shí)間復(fù)雜度為nlog2n

本篇文章就到這里了，希望能給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！

您可能感興趣的文章: