Python 算法 | 簡介

什么是算法絮缅?
  算法(Algorithm)是指解題方案的準確而完整的描述鲤竹,是一系列解決問題的清晰指令蕉汪,算法代表著用系統(tǒng)的方法描述解決問題的策略機制。也就是說封字,能夠對一定規(guī)范的輸入黔州,在有限時間內獲得所要求的輸出。不同的算法可能用不同的時間阔籽、空間或效率來完成同樣的任務流妻。一個算法的優(yōu)劣可以用空間復雜度與時間復雜度來衡量。

算法(Algorithm):一個計算過程笆制,解決問題的方法绅这。

算法復雜度分為時間復雜度和空間復雜度。其作用: 時間復雜度是指執(zhí)行算法所需要的計算工作量在辆;而空間復雜度是指執(zhí)行這個算法所需要的內存空間证薇。(算法的復雜性體現在運行該算法時的計算機所需資源的多少上,計算機資源最重要的是時間和空間(即寄存器資源匆篓,因此復雜度分為時間和空間復雜度)浑度。當然,不作特殊說明鸦概,我們一般討論的是該算法的最壞時間復雜度和最壞空間復雜度箩张,即分析最壞情況以估算算法的執(zhí)行時間的上界。

1. 時間復雜度

我們一般采用大O漸進表示法描述一個算法的時間復雜度窗市。時間復雜度主要討論的是算法執(zhí)行的次數先慷。****時間復雜度是用來估計算法運行時間的一個式子(單位)。一般來說咨察,時間復雜度高的算法比復雜度低的算法慢论熙。

一般算法時間復雜度O(n)的表示方法:
(1)用常數1取代運行時間中的所有加法常數 ;
(2)在修改后的運行次數函數中摄狱,只保留最高階項赴肚;(大單位后面不掛小單位)
(3)如果最高階項系數存在且不是1素跺,則去除與這個項相乘的常數;(去掉系數
(4)遞歸算法的時間復雜度 ==** 遞歸總次數每次遞歸的次數*
  空間復雜度 == 遞歸的深度(即樹的高度)
(5)常見的時間復雜度(按效率排序)

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)

(6)不常見的時間復雜度(看看就好)

O(n!) O(2n) O(nn) …

如何一眼判斷時間復雜度誉券?

  • 沒有循環(huán)O(1)指厌;
  • 循環(huán)減半的過程?O(logn);
  • 幾層循環(huán)就是n的幾次方的復雜度(舍棄小項)踊跟;
image

復雜度通稱為O(n)
T(n):時間復雜度Time
S(n):空間復雜度Space

名詞解釋:
  n:問題的規(guī)模,重復執(zhí)行的次數
  T(n):一段程序運行,各種操作代碼所執(zhí)行的總次數
  f(n): 存在的某個函數,使得T(n)/f(n)=非零常數, 那么f(n)稱為T(n)的同數量級函數
  O:大O符號,一種符號,表示漸進于無窮的行為

穿起來:
  算法中各種代碼操作所執(zhí)行的總次數用T(n)表示,存在某個函數f(n),使得T(n)/f(n)=非零常數,那么f(n)稱為T(n)的同數量級函數(類想一下,在坐標軸中,當入參n趨于無窮時,兩條曲線的商為常數),即:T(n)=O(f(n)),O(f(n))就是時間復雜度.O符號表示一個漸進常數. 在這個函數中可以忽略低階項和首項系數,中文例二解釋.

image
image

時間復雜度只是估計踩验,結果O(n2) 相同,不一定時間相同規(guī)模商玫,計算機運算速度箕憾。

image

O(logn)是非常快的一種算法拳昌,以上面64為例袭异,更接近O(1)。所以炬藤,一個算法如果能優(yōu)化成O(logn)御铃,是非常快的沈矿。

注意:循環(huán)減半和數值減一的區(qū)別

# 循環(huán)減半上真,每次運行,循環(huán)次數就減掉一半log2n
while n > 1:
    print(n)
    n = n // 2

# 數值減一羹膳。因為步長為2睡互,所以,是減掉了1陵像,時間復雜度為1/2n就珠,不要系數,所以時間復雜度為O(n)
for i in range(0,n,2):
    print('Hello World')
# 時間復雜度O(n3logn)
for i in range(n):
    for i in range(n):
        for i in range(n):
                print('Hello World')     # 到這是三層
    while n:
        n = n // 2
        for i in range(n):
            for i in range(n):
                print('Hello World')    # 到這是四層

解釋:while的時間復雜度是O(nlogn),比O(1)大

2. 空間復雜度

空間復雜度:即程序中變量的個數

3. 排序的穩(wěn)定性

穩(wěn)定性
① 定義:能保證兩個相等的數醒颖,經過排序之后妻怎,其在序列的前后位置順序不變。(A1=A2图贸,排序前A1在A2前面蹂季,排序后A1還在A2前面)
② 意義:穩(wěn)定性本質是維持具有相同屬性的數據的插入順序冕广,如果后面需要使用該插入順序排序疏日,則穩(wěn)定性排序可以避免這次排序。

比如撒汉,公司想根據“能力”和“資歷”(以進入公司先后順序為標準)作為本次提拔的參考沟优,假設A和B能力相當,如果是穩(wěn)定性排序睬辐,則第一次根據“能力”排序之后挠阁,就不需要第二次根據“”資歷

排序了宾肺,因為“資歷”排序就是員工插入員工表的順序。如果是不穩(wěn)定排序侵俗,則需要第二次排序锨用,會增加系統(tǒng)開銷。

分類
① 穩(wěn)定性排序:冒泡排序隘谣,插入排序增拥、歸并排序、基數排序
② 不穩(wěn)定性排序:選擇排序寻歧、快速排序掌栅、希爾排序、堆排序

例析
(1)穩(wěn)定性排序
① 冒泡排序
  冒泡排序本質是码泛,從左到右開始不斷把大的元素往后調(或者猾封,從右往左開始不斷把小的元素往前調)。比較是比較相鄰的兩個元素噪珊,交換也是發(fā)生在這兩個元素之間晌缘。所以,如果兩個元素相等卿城,你總不會無聊地把它倆交換一下吧枚钓。如果兩個相等元素沒有相鄰,那么也會經過一波兩兩交換使他們相鄰瑟押,此時也不會發(fā)生交換搀捷。

② 插入排序
  插入排序本質是,在一個已經有序的小序列基礎上多望,通過從右往左比較嫩舟,一次插入一個元素。剛開始這個小序列只有一個元素怀偷。比較是從有序序列的末尾開始家厌,想插入的元素和已經有序的最大者開始比較,如果比它大則直接插在其后面椎工,否則一直往前比較饭于,直到找到比它小的或與它相等的,然后插在其后面维蒙。

③ 歸并排序
  歸并排序本質是掰吕,把序列遞歸地分成短序列,遞歸出口是短序列只有1個元素(此時認為直接有序)或者2個序列(1次比較和交換)颅痊,然后把各個有序的短序列合并成一個有序的長序列殖熟,不斷合并直到原序列全部排好序。當存在1個或2個元素時斑响,1個元素不會交換菱属,2個元素如果大小相等也沒有人故意交換钳榨,因此不會破壞穩(wěn)定性。那么在短的有序序列合并的過程中纽门,穩(wěn)定是否受到破壞薛耻?沒有。合并過程中當兩個當前元素相等時赏陵,處在前面序列的元素依然保存在結果序列的前面昭卓。

④ 基數排序
  基數排序本質是,按照低位先排序瘟滨,然后收集候醒,再按照高位排序,然后再收集杂瘸,依次類推倒淫,直到最高位。比如序列“171(1),331,171(2)”败玉,低位排序(個位)結果是“171(1),331,171(2)”敌土,高位排序(十位)結果是“331171(1),171(2)”,高位排序(百位)結果是“171(1),171(2),331”运翼。

(2)不穩(wěn)定性排序
① 選擇排序
  選擇排序本質是返干,給每個位置選擇剩下元素中最小的。比如給第一個位置選擇最小的血淌,給第二個位置選擇剩余元素里面第二小的矩欠,依次類推。例如序列“5(1),8,5(2),2,9”悠夯,5(1)會和2交換癌淮,破壞穩(wěn)定性。

② 快速排序
  快速排序本質是沦补,選取第一個元素為中樞元素a[center_index](index=0)乳蓄。從兩個方向入手,首先左邊的i下標一直往右走夕膀,當a[i] > a[center_index]停止虚倒,由右邊的j下標開始往左走,當a[j] <= a[center_index]停止产舞,由左邊i下標開始剛才的表演魂奥,重復上面的過程,直到i>j庞瘸,交換a[j]和a[center_index]捧弃,完成一趟快速排序赠叼。在中樞元素和a[j]交換的時候擦囊,很有可能把前面的元素的穩(wěn)定性打亂违霞,比如序列為 “5,3(1),4,3(2),8,11,9”, 現在中樞元素5和3(2)交換就會把元素3的穩(wěn)定性打亂瞬场。不穩(wěn)定發(fā)生在中樞元素和a[j]交換的時刻买鸽。

③ 希爾排序
  希爾排序本質是,按照不同步長對元素進行插入排序贯被,當剛開始元素很無序的時候眼五,步長最大,所以插入排序的元素個數很少彤灶,速度很快看幼;當元素基本有序了,步長很小幌陕,插入排序對于有序的序列效率很高诵姜。所以,希爾排序的時間復雜度會比o(n^2)好一些搏熄。由于多次插入排序棚唆,我們知道一次插入排序是穩(wěn)定的,不會改變相同元素的相對順序心例,但在不同的插入排序過程中宵凌,相同的元素可能在各自的插入排序中移動,最后其穩(wěn)定性就會被打亂止后,所以shell排序是不穩(wěn)定的瞎惫。

④ 堆排序
  堆排序本質是,我們知道堆的結構是節(jié)點i的孩子為2i和2i+1節(jié)點译株,大頂堆要求父節(jié)點大于等于其2個子節(jié)點微饥,小頂堆要求父節(jié)點小于等于其2個子節(jié)點。在一個長為n的序列古戴,堆排序的過程是從第n/2開始和其子節(jié)點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩(wěn)定性欠橘。但當為n/2-1, n/2-2, ...1這些個父節(jié)點選擇元素時,就會破壞穩(wěn)定性现恼。有可能第n/2個父節(jié)點交換把后面一個元素交換過去了肃续,而第n/2-1個父節(jié)點把后面一個相同的元素沒有交換,那么這2個相同的元素之間的穩(wěn)定性就被破壞了叉袍。所以始锚,堆排序不是穩(wěn)定的排序算法。

排序算法時間的復雜度和空間復雜度

image.png
?著作權歸作者所有,轉載或內容合作請聯系作者
  • 序言:七十年代末喳逛,一起剝皮案震驚了整個濱河市瞧捌,隨后出現的幾起案子,更是在濱河造成了極大的恐慌,老刑警劉巖姐呐,帶你破解...
    沈念sama閱讀 221,635評論 6 515
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件殿怜,死亡現場離奇詭異,居然都是意外死亡曙砂,警方通過查閱死者的電腦和手機头谜,發(fā)現死者居然都...
    沈念sama閱讀 94,543評論 3 399
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來鸠澈,“玉大人柱告,你說我怎么就攤上這事⌒Τ拢” “怎么了际度?”我有些...
    開封第一講書人閱讀 168,083評論 0 360
  • 文/不壞的土叔 我叫張陵,是天一觀的道長涵妥。 經常有香客問我甲脏,道長,這世上最難降的妖魔是什么妹笆? 我笑而不...
    開封第一講書人閱讀 59,640評論 1 296
  • 正文 為了忘掉前任块请,我火速辦了婚禮,結果婚禮上拳缠,老公的妹妹穿的比我還像新娘墩新。我一直安慰自己,他們只是感情好窟坐,可當我...
    茶點故事閱讀 68,640評論 6 397
  • 文/花漫 我一把揭開白布海渊。 她就那樣靜靜地躺著,像睡著了一般哲鸳。 火紅的嫁衣襯著肌膚如雪臣疑。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,262評論 1 308
  • 那天徙菠,我揣著相機與錄音讯沈,去河邊找鬼。 笑死婿奔,一個胖子當著我的面吹牛缺狠,可吹牛的內容都是我干的。 我是一名探鬼主播萍摊,決...
    沈念sama閱讀 40,833評論 3 421
  • 文/蒼蘭香墨 我猛地睜開眼挤茄,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了冰木?” 一聲冷哼從身側響起穷劈,我...
    開封第一講書人閱讀 39,736評論 0 276
  • 序言:老撾萬榮一對情侶失蹤笼恰,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后歇终,有當地人在樹林里發(fā)現了一具尸體社证,經...
    沈念sama閱讀 46,280評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,369評論 3 340
  • 正文 我和宋清朗相戀三年练湿,在試婚紗的時候發(fā)現自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片审轮。...
    茶點故事閱讀 40,503評論 1 352
  • 序言:一個原本活蹦亂跳的男人離奇死亡肥哎,死狀恐怖,靈堂內的尸體忽然破棺而出疾渣,到底是詐尸還是另有隱情篡诽,我是刑警寧澤,帶...
    沈念sama閱讀 36,185評論 5 350
  • 正文 年R本政府宣布榴捡,位于F島的核電站,受9級特大地震影響,放射性物質發(fā)生泄漏蒿讥。R本人自食惡果不足惜挂绰,卻給世界環(huán)境...
    茶點故事閱讀 41,870評論 3 333
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望项乒。 院中可真熱鬧啰劲,春花似錦、人聲如沸檀何。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,340評論 0 24
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽频鉴。三九已至栓辜,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間垛孔,已是汗流浹背藕甩。 一陣腳步聲響...
    開封第一講書人閱讀 33,460評論 1 272
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留周荐,地道東北人辛萍。 一個月前我還...
    沈念sama閱讀 48,909評論 3 376
  • 正文 我出身青樓,卻偏偏與公主長得像羡藐,于是被迫代替她去往敵國和親贩毕。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,512評論 2 359

推薦閱讀更多精彩內容

  • 1)這本書為什么值得看: Python語言描述仆嗦,如果學的Python用這本書學數據結構更合適 2016年出版辉阶,內容...
    孫懷闊閱讀 12,506評論 0 15
  • 歡迎訪問我的博客原文??????鄭重聲明:轉載請務必注明出處! 排序算法是程序員必備的基礎知識,弄明白它們的原理和...
    FiTeen閱讀 894評論 0 0
  • 概述 排序有內部排序和外部排序谆甜,內部排序是數據記錄在內存中進行排序垃僚,而外部排序是因排序的數據很大,一次不能容納全部...
    zwb_jianshu閱讀 1,156評論 0 0
  • 概述 排序有內部排序和外部排序规辱,內部排序是數據記錄在內存中進行排序谆棺,而外部排序是因排序的數據很大,一次不能容納全部...
    閑云清煙閱讀 758評論 0 6
  • 考研復習大綱 數學 三月~六月初(一輪復習) 復習目標:過一遍考研數學一的全部內容(包括高等數學上罕袋,下改淑,概率論,線...
    joker_luo閱讀 127評論 0 1