目錄

1.1 什么是算法

1.2 算法設(shè)計(jì)技術(shù)

1.2.1 數(shù)據(jù)維度

1.3 性能分析

1.3.1 空間復(fù)雜度分析

1.3.2 時(shí)間復(fù)雜度分析

1.3.3 性能評估

1.3.4 選擇算法

1.3.5 大O記號

1.3.6 驗(yàn)證算法

1.4 驗(yàn)證算法

1.4.1 精確算法、近似算法

1.4.2 可解釋性

2. 算法中的數(shù)據(jù)結(jié)構(gòu)

2.1 python中的數(shù)據(jù)結(jié)構(gòu)

2.2 抽象數(shù)據(jù)類型

1.1 什么是算法

算法是求解問題的計(jì)算規(guī)則集,，旨在根據(jù)精確定義的指令,，為任何有效輸入產(chǎn)生對應(yīng)的輸出結(jié)果。

算法設(shè)計(jì)致力于設(shè)計(jì)一種最高效的數(shù)學(xué)步驟,，來有效求解實(shí)際問題,。以所得的數(shù)學(xué)步驟為基礎(chǔ)，可以開發(fā)一個(gè)可復(fù)用且通用性更強(qiáng)的數(shù)學(xué)方案來求解更廣泛的問題。

開發(fā)階段由兩個(gè)步驟組成：

1.設(shè)計(jì)

要構(gòu)思算法的架構(gòu),、邏輯和實(shí)現(xiàn)細(xì)節(jié),，形成文檔。

設(shè)計(jì)過程是一個(gè)迭代的過程,，需要對各種候選算法進(jìn)行比較,。

恰當(dāng)?shù)乃惴ú粌H具有令人滿意的性能，還有令人信服的準(zhǔn)確性,。

2.編碼

將設(shè)計(jì)好的算法結(jié)構(gòu)轉(zhuǎn)為計(jì)算機(jī)程序,，實(shí)際程序必須實(shí)現(xiàn)設(shè)計(jì)階段提出的所有邏輯和結(jié)構(gòu)。

算法的設(shè)計(jì)階段和編碼階段本質(zhì)上是一個(gè)迭代的過程,，需要設(shè)計(jì)出同時(shí)滿足功能需求和非功能需求,。

• 功能需求：明確刻畫給定輸入數(shù)據(jù)對應(yīng)的正確輸出結(jié)果。

• 非功能需求：在給定數(shù)據(jù)規(guī)模上的性能需求,。

1.2 算法設(shè)計(jì)技術(shù)

一、算法是否能產(chǎn)生預(yù)期的結(jié)果,？

二,、這是獲取預(yù)期結(jié)果的最佳方法嗎？

三,、算法在更大的數(shù)據(jù)集上表現(xiàn)的怎么樣,？

一般來說，算法可根據(jù)問題的特點(diǎn)分為以下類型：

1. 數(shù)據(jù)密集型

   數(shù)據(jù)密集型算法旨在處理大量數(shù)據(jù),，其處理需求相對簡單,。壓縮大型文件就是一個(gè)典型的例子。

   對于這類算法,，待處理數(shù)據(jù)的規(guī)模遠(yuǎn)大于引擎的內(nèi)存規(guī)模,，因此可能需要開發(fā)一個(gè)迭代處理設(shè)計(jì)來高效的處理數(shù)據(jù)。

2. 計(jì)算密集型

   計(jì)算密集型具有大量計(jì)算需求而不涉及大量數(shù)據(jù),。一個(gè)簡單的例子就是尋找大素?cái)?shù)的算法,。尋找恰當(dāng)策略將算法劃分為不同的階段，使其中至少有一個(gè)階段是可以并行化的,，這是最大限度提升算法性能的關(guān)鍵,。

3. 數(shù)據(jù)和計(jì)算密集型

   有些算法需要處理大量數(shù)據(jù)，同時(shí)也有大量計(jì)算需求,。實(shí)時(shí)視頻信號上的情感分析算法就是一個(gè)很好的例子,，其中數(shù)據(jù)和計(jì)算需求都很大。這類算法是最耗費(fèi)資源的算法,，需要對算法進(jìn)行精心設(shè)計(jì),，并對可用資源進(jìn)行智能分配。

1.2.1 數(shù)據(jù)維度

將算法從問題的數(shù)據(jù)維度上進(jìn)行歸類，需要查看數(shù)據(jù)的體積,、速度,、多樣性

• 體積

  要處理的數(shù)據(jù)的預(yù)期規(guī)模

• 速度

  使用該算法是新數(shù)據(jù)生成的預(yù)期速度?？梢詾?

• 多樣性

  量化了所設(shè)計(jì)算法預(yù)計(jì)要處理多種不同類型的數(shù)據(jù),。

1.3 性能分析

算法的性能分析是算法設(shè)計(jì)的重要部分。估計(jì)算法性能的方法之一是分析算法的復(fù)雜度,。

復(fù)雜度理論研究算法的復(fù)雜程度,。任何有用的算法應(yīng)該具備以下三個(gè)關(guān)鍵特征：

• 算法應(yīng)該是正確的；

• 好算法應(yīng)該是易懂的,；

• 好算法應(yīng)該是高效的

有兩種方法用于量化分析算法的復(fù)雜度：

• 空間復(fù)雜度：估計(jì)算法運(yùn)行對內(nèi)存的需求

• 時(shí)間復(fù)雜度：估計(jì)算法運(yùn)行的時(shí)間

1.3.1 空間復(fù)雜度分析

空間復(fù)雜度分析就是估計(jì)算法在處理輸入數(shù)據(jù)時(shí)所需的內(nèi)存量,。

在處理輸入數(shù)據(jù)的同時(shí)，算法需要在內(nèi)存中存儲(chǔ)一些臨時(shí)的數(shù)據(jù)結(jié)構(gòu),。算法的設(shè)計(jì)方式將會(huì)影響這些數(shù)據(jù)結(jié)構(gòu)的數(shù)量,、類型和規(guī)模。在分布式計(jì)算時(shí)代,，需要處理的數(shù)據(jù)量越來越大,，空間復(fù)雜度分析變得日益重要。這些數(shù)據(jù)結(jié)構(gòu)的規(guī)模,、類型和數(shù)量將決定對于底層硬件的內(nèi)存需求

1.3.2 時(shí)間復(fù)雜度分析

時(shí)間復(fù)雜度分析就是依據(jù)算法結(jié)構(gòu)來估計(jì)算法完成其指定工作所需的時(shí)間,。與空間復(fù)雜度不同，時(shí)間復(fù)雜度并不取決于運(yùn)行算法的任何硬件設(shè)施,，而是完全取決于算法本身的結(jié)構(gòu),。

時(shí)間復(fù)雜度分析的總體目標(biāo)是試圖回答下列重要問題：算法是否具有良好的可擴(kuò)展性？算法在處理更大規(guī)模數(shù)據(jù)集時(shí)性能如何變化,？

在很多情況下,，設(shè)計(jì)算法的方法可能不止一種，此時(shí),，時(shí)間復(fù)雜度分析的目的為：給定某個(gè)問題和多種算法,，從時(shí)間效率來看，使用哪種算法效率最高,？

計(jì)算算法的時(shí)間復(fù)雜度有以下兩種基本方法：

• 實(shí)現(xiàn)算法后的分析方法：這種方法先分別實(shí)現(xiàn)各種候選算法,，再對其性能進(jìn)行比較。

• 實(shí)現(xiàn)算法前的理論方法：這種方法在運(yùn)行算法前用數(shù)學(xué)方法近似計(jì)算每個(gè)算法的性能,。

1.3.3 性能評估

典型算法的性能都取決于作為輸入提供給它的數(shù)據(jù)的類型,。例如，如果在待求解問題中數(shù)據(jù)已經(jīng)排序,，則該算法執(zhí)行的速度可能會(huì)快得驚人,。如果用排序后的輸入作為基準(zhǔn)來對特定算法進(jìn)行測試,，則將得到不真實(shí)的、過好的性能測試結(jié)果,，而這個(gè)結(jié)果在大多數(shù)情況下并不能夠反映算法的實(shí)際性能,。為了處理算法對輸入數(shù)據(jù)的這種依賴性，我們在進(jìn)行性能分析時(shí)需要考慮各種不同情況,。

• 最好復(fù)雜度

在最好復(fù)雜度中,，輸入數(shù)據(jù)經(jīng)過組織，能夠得到算法的最佳性能,。最好復(fù)雜度分析得出算法性能的上界,。

• 最壞復(fù)雜度

評估算法性能的第二種方法是嘗試找到算法在給定條件下完成工作所需的最大可能時(shí)間。最壞復(fù)雜度分析非常有用,，因?yàn)槲覀兛梢员ＷC無論在何種條件下算法的性能總是優(yōu)于所得的分析結(jié)果,。在評估算法在處理更大規(guī)模數(shù)據(jù)集的復(fù)雜問題時(shí)，最壞復(fù)雜度分析特別有用,。最壞復(fù)雜度給出了算法性能的下界,。

• 平均復(fù)雜度

平均復(fù)雜度分析先將各種可能的輸入劃分為不同的組，然后從每組中選擇具有代表性的一個(gè)輸入來分析算法性能,，最后計(jì)算出算法在各組輸入上的平均性能,。平均復(fù)雜度并不總是準(zhǔn)確結(jié)果，因?yàn)樗枰紤]算法輸入的所有不同組合和可能性,，但這并不總是容易做到的。

1.3.4 選擇算法

你怎么知道哪種方案更好,？你怎么知道哪種算法運(yùn)行得更快,？時(shí)間復(fù)雜度和大O記號（大O表示法）為回答這種問題提供了有效手段。

為了理解它的作用,，我們舉一個(gè)簡單的例子：對一個(gè)數(shù)字列表進(jìn)行排序,。有幾種可用的算法可以完成這項(xiàng)工作，問題是如何選擇合適的算法,。

如果列表中數(shù)字不多,，那我們選擇哪種算法來排序根本無關(guān)緊要。但是如果列表規(guī)模非常高,，則選擇合適的算法就會(huì)產(chǎn)生區(qū)別,。一個(gè)很差的算法甚至可能需要幾個(gè)小時(shí)才能完成列表排序任務(wù)，而一個(gè)設(shè)計(jì)較好的算法則可能僅用幾秒完成了任務(wù),。因此,，在大規(guī)模輸入數(shù)據(jù)集上，投入時(shí)間和精力展開性能分析,，選擇合理設(shè)計(jì)的算法來高效地完成要求的任務(wù)是非常有意義的,。

1.3.5 大O記號

大O記號用于量化表示各種算法在輸入規(guī)模增長時(shí)的性能,，它是最壞復(fù)雜度分析中最常用的方法之一。

常數(shù)時(shí)間復(fù)雜度（O（1））

如果算法運(yùn)行時(shí)間是獨(dú)立于輸入數(shù)據(jù)規(guī)模的相同值,，則稱其運(yùn)行時(shí)間是常數(shù)時(shí)間,，表示為O(1)。

線性時(shí)間復(fù)雜度（O(n)）

如果算法的執(zhí)行時(shí)間與輸入規(guī)模成正比,，則稱該算法具有線性時(shí)間復(fù)雜度,，表示為O(n)。

平方時(shí)間復(fù)雜度（O(n2)）

如果算法的執(zhí)行時(shí)間與輸入規(guī)模的平方成正比,，則稱該算法的運(yùn)行時(shí)間為平方時(shí)間,。

對數(shù)時(shí)間復(fù)雜度（O(log n)）

如果算法的執(zhí)行時(shí)間與輸入規(guī)模的對數(shù)成正比，則稱該算法的運(yùn)行時(shí)間為對數(shù)時(shí)間,。在時(shí)間復(fù)雜度為O(log n)的算法中,，隨著算法的每一輪迭代，輸入規(guī)模都會(huì)以常數(shù)倍數(shù)遞減,。

1.3.6 驗(yàn)證算法

驗(yàn)證算法指的是確保它是為待求解問題找到了一個(gè)數(shù)學(xué)求解方案,。驗(yàn)證過程應(yīng)該在盡可能多的輸入值和輸入類型上檢驗(yàn)求解結(jié)果。

1.4 驗(yàn)證算法

驗(yàn)證算法指的是確保它是為待求解問題找到了一個(gè)數(shù)學(xué)求解方案,。驗(yàn)證過程應(yīng)該在盡可能多的輸入值和輸入類型上檢驗(yàn)求解結(jié)果,。

1.4.1 精確算法、近似算法

精確算法：預(yù)計(jì)在不引進(jìn)任何假設(shè)或近似的情況下產(chǎn)生精確解,。

近似算法：當(dāng)問題的復(fù)雜度過大,，在給定的資源下難以處理時(shí)，我們會(huì)通過一些假設(shè)來簡化問題,。

1.4.2 可解釋性

有些特征會(huì)直接或間接用于得到某種特定決策,，能夠準(zhǔn)確識(shí)別出這些特征的能力，稱為算法的可解釋性,。算法在臨界條件下使用,，需要評估算法是否存在偏差和偏見。如果算法可能影響到與人們生活相關(guān)的決策,，則算法的倫理分析將會(huì)成為驗(yàn)證過程中的標(biāo)準(zhǔn)環(huán)節(jié),。

2. 算法中的數(shù)據(jù)結(jié)構(gòu)

算法需要必要的內(nèi)存數(shù)據(jù)結(jié)構(gòu)，用于在執(zhí)行時(shí)保存臨時(shí)數(shù)據(jù),。選擇恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)對算法高效執(zhí)行至關(guān)重要.

2.1 python中的數(shù)據(jù)結(jié)構(gòu)

列表（list）：有序的可變元素序列,。

元組（tuple）：有序的不可變元素序列。

集合（set）：無序元素序列（其中元素不重復(fù)）,。

字典（dictionary）：無序的鍵值對序列,。

數(shù)據(jù)幀（Data Frame）：存儲(chǔ)二維數(shù)據(jù)的二維結(jié)構(gòu)。

2.1.1 列表

在Python中,，列表是用來存儲(chǔ)可變元素序列的主要數(shù)據(jù)結(jié)構(gòu),。列表中儲(chǔ)存的元素不必是同一類型的,。

a = [1,3,'你好','Hello',[2,4],{2,5}]
print(type(a))  # a的類型
print(a)
----------------------------------------------------------------
<class 'list'>
[1, 3, '你好', 'Hello', [2, 4], {2, 5}]

列表是Python中非常流行的一維數(shù)據(jù)結(jié)構(gòu)之一。它在各個(gè)場景中都十分有用,。

迭代：Python中允許for循環(huán)對列表里的每個(gè)元素進(jìn)行迭代

a = [1,3,'你好','Hello',[2,4],{2,5}]
for i in a:
    print(i)
?
1
3
你好
Hello
[2, 4]
{2, 5}

lambda函數(shù)：也稱匿名函數(shù),。lambda函數(shù)在算法中特別重要，其提供了動(dòng)態(tài)創(chuàng)建函數(shù)的能力,。

• 過濾數(shù)據(jù)：為了過濾數(shù)據(jù),，需要定義一個(gè)謂詞，說明需要完成什么工作,，他是輸入一個(gè)參數(shù)并返回一個(gè)布爾值的函數(shù)

a = [1,2,3,4,5,6,7,8,9]
b = filter(lambda i:i % 2 == 0,a)
print(list(b))
----------------------------------------------------------------
[2, 4, 6, 8]

在這段代碼中,，我們使用了lambda函數(shù)來過濾一個(gè)列表，該函數(shù)指定了過濾標(biāo)準(zhǔn),。filter函數(shù)旨在依據(jù)定義的標(biāo)準(zhǔn)從序列中過濾掉不符合標(biāo)準(zhǔn)的元素,。

• 數(shù)據(jù)轉(zhuǎn)換：map()函數(shù)可用于lambda函數(shù)進(jìn)行數(shù)據(jù)轉(zhuǎn)換

a = [1,2,3,4,5,6,7,8,9]
b = map(lambda x : x * 2,a)
print(list(b))
----------------------------------------------------------------
[2, 4, 6, 8, 10, 12, 14, 16, 18]

• 數(shù)據(jù)聚合:可以用reduce()函數(shù)，該函數(shù)會(huì)對循環(huán)運(yùn)行定義的函數(shù),，對列表中每對元素進(jìn)行處理

from functools import reduce
def doSum(x1,x2):
    return x1 + x2
a = [1,2,3,4,5,6,7,8]
x = reduce(doSum,a)
print(x)
----------------------------------------------------------------
36

• 列表的時(shí)間復(fù)雜度

  可用大O表示法來表示

  功能	時(shí)間復(fù)雜度
  插入一個(gè)元素	O(1)
  刪除一個(gè)元素	O(n)
  列表切片	O(n)
  元素檢索	O(n)
  復(fù)制	O(n)

  添加單個(gè)元素所需的時(shí)間與列表的規(guī)模無關(guān),，而表格中其他操作的復(fù)雜度取決于列表的規(guī)模。列表的規(guī)模越大,，性能受到的影響就越明顯,。

2.1.2 元組

與列表相反，元組是不可變的（只讀）數(shù)據(jù)結(jié)構(gòu),。

a = (1,2,3,4,5,6,7,(1,3,4,6,8),8,9)
print(type(a))
print(a[2:8])
----------------------------------------------------------------
(3, 4, 5, 6, 7, (1, 3, 4, 6, 8))

元組的時(shí)間復(fù)雜度：O(1)

元組是不可變的數(shù)據(jù)類型,，其中沒有append函數(shù)。,。

2.1.3字典

以鍵值對的形式保存數(shù)據(jù)是非常重要的,，尤其在分布式算法中。

要?jiǎng)?chuàng)建一個(gè)字典,，應(yīng)該選擇一個(gè)在整個(gè)數(shù)據(jù)處理過程最適合識(shí)別數(shù)據(jù)的屬性作為鍵,。值可以是任何類型的元素,。

Python總是使用復(fù)雜的數(shù)據(jù)類型（如列表）作為值,。

a = {
    'color':'red',
    'age':18,
    'gender':'man',
    'classmate':['小李','小方','小王','小張']
}
print(a)
print(a.get('age')) # 通過鍵查找值
?
for k,v in a.items():   # 通過值查找鍵
    if v == 'red':
        print(k)
----------------------------------------------------------------
{'color': 'red', 'age': 18, 'gender': 'man', 'classmate': ['小李', '小方', '小王', '小張']}
18
color

字典的時(shí)間復(fù)雜度

獲取或設(shè)置鍵值所需的時(shí)間和字典的大小無關(guān)。這意味著,，將一個(gè)鍵值對添加到一個(gè)大小為3的字典中所花費(fèi)的時(shí)間與將一個(gè)鍵值對添加到一個(gè)大小為100萬的字典中所花費(fèi)的時(shí)間是一樣的,。

2.1.4 集合

集合被定義為元素集，可以是不同類型的元素,。

a = {2,4,6,8,10,55}
b = {1,3,5,7,9,55}
print(a|b)  # 并集  
print(a&b)  # 交集
----------------------------------------------------------------
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 55}
{55}

集合的時(shí)間復(fù)雜度

增刪元素所需的時(shí)間與該集合的大小無關(guān),。

2.1.5 數(shù)據(jù)幀

數(shù)據(jù)幀是Python中pandas包中的一種數(shù)據(jù)結(jié)構(gòu)，用來存儲(chǔ)可用的表格數(shù)據(jù),。

import pandas as pd
?
df = pd.DataFrame([
    [1,'小李',23,'女'],
    [2,'小張',23,'男'],
    [3,'小王',22,'女'],
    [4,'小趙',25,'男']
])
df.columns = ['序號','姓名','年齡','性別']
print(df)
----------------------------------------------------------------
  序號  姓名  年齡 性別
0   1  小李  23  女
1   2  小張  23  男
2   3  小王  22  女
3   4  小趙  25  男
print(df[['姓名','性別']])# 檢索
----------------------------------------------------------------
0  小李  女
1  小張  男
2  小王  女
3  小趙  男

數(shù)據(jù)幀術(shù)語

軸：在pandas文檔中,，一個(gè)數(shù)據(jù)幀的單列或單行稱為軸,。

軸族：如果軸的數(shù)量大于1，則它們作為一組,，稱為軸族,。

標(biāo)簽：數(shù)據(jù)幀允許用標(biāo)簽來命名列和行。

2.1.6 矩陣

矩陣是一種具有固定列數(shù)和行數(shù)的二維數(shù)據(jù)結(jié)構(gòu),，矩陣中的每個(gè)元素都可以通過指定它的列和行來引用,。

在Python中，可以通過用numpy中的array函數(shù)來創(chuàng)建矩陣,。

import numpy as np
?
x = np.array([[11,12,13],[21,22,23],[31,32,33]])
print(x)
print(type(x))
----------------------------------------------------------------
<class 'numpy.ndarray'>

在多媒體數(shù)據(jù)處理中經(jīng)常使用矩陣運(yùn)算,。

2.2 抽象數(shù)據(jù)類型

通常來說，抽象是一個(gè)概念,，用來定義復(fù)雜系統(tǒng)中常見的核心功能,。利用這個(gè)概念來創(chuàng)建通用的數(shù)據(jù)結(jié)構(gòu)，就產(chǎn)生了抽象數(shù)據(jù)類型（ADT）

2.2.1 向量

向量是一種存儲(chǔ)數(shù)據(jù)的單維結(jié)構(gòu),，這是Python中最流行的數(shù)據(jù)結(jié)構(gòu)之一,。Python中創(chuàng)建向量有兩種方法：

• 創(chuàng)建向量的最簡單方法是使用Python的列表。

• 使用numpy數(shù)組：用numpy中的array函數(shù),。

  未完待續(xù)

  ---