? ? ? ? 歸并排序是證明計算復(fù)雜度領(lǐng)域的一個重要結(jié)論的基礎(chǔ)，而計算復(fù)雜性能夠幫助我們理解排序自身固有的難易程度。計算復(fù)雜性在算法設(shè)計中扮演著非常重要的角色。
? ? ? ? 研究復(fù)雜度的第一步是建立一個計算模型。一般來說，研究者會盡量尋找一個和問題相關(guān)的最簡單的模型。對排序來說，研究對象是基于比較的算法，它們對數(shù)組元素的操作方式是由主鍵的比較決定的。一個基于比較的算法在兩次比較之間可能會進(jìn)行任意規(guī)模的計算，但它只能通過主鍵之間的比較得到某個主鍵的信息。
? ? ? ? 沒有任何基于比較的算法能夠保證使用少于lg(N!)~NlgN次比較將長度為N的數(shù)組排序。
? ? ? ? 歸并排序是一種漸進(jìn)最優(yōu)的基于比較排序的算法。
? ? ? ? 需要強(qiáng)調(diào)的是，和計算模型一樣，我們需要精確地定義最優(yōu)算法，在適用的情況下，關(guān)鍵在于計算復(fù)雜度會影響優(yōu)秀軟件的開發(fā)。
? ? ? ? 歸并排序的最優(yōu)性并不是結(jié)束，因?yàn)檫€有些其他情況：
? ? ? ? 1、歸并排序的空間復(fù)雜度不是最優(yōu)的
? ? ? ? 2、在實(shí)踐中不一定會遇到最壞情況
? ? ? ? 3、除了比較，算法的其他操作也可能很重要，比如訪問數(shù)組文章來源：http://www.zghlxwxcb.cn/news/detail-811055.html
? ? ? ? 4、不進(jìn)行比較也能將某些數(shù)據(jù)排序。文章來源地址http://www.zghlxwxcb.cn/news/detail-811055.html
到了這里，關(guān)于【排序算法】排序算法的復(fù)雜度的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
