冒泡排序原理和實(shí)現(xiàn)
1）算法的概念
2）時(shí)間復(fù)雜度和空間復(fù)雜度的概念
3）常見的排序算法和查找算法
時(shí)間復(fù)雜度和空間復(fù)雜度的概念
算法評(píng)定：
1）算法分析的目的在于選擇合適的算法和改進(jìn)算法
2）一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮
時(shí)間復(fù)雜度：
執(zhí)行算法所需要的計(jì)算工作量台夺。一般來說爆哑，計(jì)算機(jī)算法是問題規(guī)模n的函數(shù)f(n),算法的時(shí)間復(fù)雜度也因此記做T(n) = Of(n)
問題的規(guī)模n越大如庭，算法執(zhí)行的時(shí)間增長率與f(n)的增長率相關(guān)，稱作漸進(jìn)時(shí)間復(fù)雜度
時(shí)間復(fù)雜度計(jì)算方式
O(n^2)、O(1)主慰、O(n)、？
步驟：
1）得出算法的計(jì)算次數(shù)的公式
2）用常數(shù)1來取代所有時(shí)間中的左右加法常數(shù).
3）在修改后的運(yùn)行次數(shù)函數(shù)中柔滔，只保留最高階項(xiàng)
4）如果最高階存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)
舉例：
常數(shù)階：O(1)
線性階：O(n)
平(立)方階：O(n^2) / O(n^3)
特殊平方階：O(n^2/2+n/2)->O(n^2)
對(duì)數(shù)階：O(log2n)
效率：O(1) > O(log2n) > O(n) > O(nlog2n) > O(n^2) > O(n^3) > O(2^n) > O(n!) > O(n^n)
時(shí)間復(fù)雜度其他概念
最壞情況：最壞的情況時(shí)的運(yùn)行時(shí)間萍虽，一種保證睛廊，如果沒有特別說明，說的時(shí)間復(fù)雜度即為最壞情況的時(shí)間復(fù)雜度杉编。
平均情況：期望的運(yùn)行時(shí)間
changj
空間復(fù)雜度
算法需要消耗的內(nèi)存空間超全，記做：S(n) = O(f(n))
包括程序代碼所占用的空間，輸入數(shù)據(jù)所有占用的空間和輔助變量所占用的空間這三個(gè)方面
計(jì)算和表示方式與時(shí)間復(fù)雜度類似邓馒，一般用復(fù)雜度的漸進(jìn)性來表示嘶朱。
空間復(fù)雜度的計(jì)算方式
有時(shí)用空間來換取時(shí)間
冒泡排序的元素交換，空間復(fù)雜度O(1)
常見算法和排序
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門胆萧，熙熙樓的掌柜王于貴愁眉苦臉地迎上來庆揩，“玉大人，你說我怎么就攤上這事跌穗《┥危” “怎么了？”我有些...
- 文/不壞的土叔 我叫張陵蚌吸，是天一觀的道長锈拨。 經(jīng)常有香客問我，道長羹唠，這世上最難降的妖魔是什么奕枢？ 我笑而不...
- 正文 為了忘掉前任娄昆，我火速辦了婚禮，結(jié)果婚禮上缝彬，老公的妹妹穿的比我還像新娘萌焰。我一直安慰自己，他們只是感情好谷浅，可當(dāng)我...
- 文/花漫 我一把揭開白布扒俯。 她就那樣靜靜地躺著，像睡著了一般一疯。 火紅的嫁衣襯著肌膚如雪撼玄。 梳的紋絲不亂的頭發(fā)上，一...
- 文/蒼蘭香墨 我猛地睜開眼兔院，長吁一口氣：“原來是場噩夢啊……” “哼殖卑！你這毒婦竟也來了站削？” 一聲冷哼從身側(cè)響起，我...
- 序言：老撾萬榮一對(duì)情侶失蹤孵稽，失蹤者是張志新（化名）和其女友劉穎许起，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體菩鲜，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡园细，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了接校。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片猛频。...
- 正文 年R本政府宣布毡熏，位于F島的核電站，受9級(jí)特大地震影響侣诵，放射性物質(zhì)發(fā)生泄漏痢法。R本人自食惡果不足惜狱窘，卻給世界環(huán)境...
- 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望财搁。 院中可真熱鬧蘸炸，春花似錦、人聲如沸尖奔。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽越锈。三九已至仗嗦，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間甘凭，已是汗流浹背稀拐。 一陣腳步聲響...
- 正文 我出身青樓，卻偏偏與公主長得像躲胳，于是被迫代替她去往敵國和親蜓洪。 傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 選擇排序 對(duì)于任何輸入偏形，時(shí)間為O(n*n)静袖； 冒泡排序 最優(yōu)（對(duì)于升序的數(shù)組，因?yàn)榧尤肓艘粋€(gè)跳出判斷）：O(n)壳猜，...
- [TOC]1勾徽、插入排序1.1直接插入排序（從后向前找到合適位置后插入）1.2 二分法插入排序1.3 希爾排序2、選...
- 歲月留痕（三）--燕子在我家筑巢 文/朱秋霞 我家在村最南端，三間瓦房喘帚，土墻小院畅姊，院外有柳樹、槐樹吹由、楝樹若未，院內(nèi)有棗...
