什么是算法絮缅?
算法(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的幾次方的復雜度(舍棄小項)踊跟;
復雜度通稱為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符號表示一個漸進常數. 在這個函數中可以忽略低階項和首項系數,中文例二解釋.
時間復雜度只是估計踩验,結果O(n2) 相同,不一定時間相同規(guī)模商玫,計算機運算速度箕憾。
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)定的排序算法。
排序算法時間的復雜度和空間復雜度