Python--day4--正規表達式/冒泡/時間複雜度

介紹：

本文為學習python筆記，時間為2016年12月27日。

正規表達式

概念

基本文法

比對格式

常用5種操作

字元比對

compile格式

實際應用

冒泡算法

時間複雜度

概念：

正規表達式，又稱規則表達式。比對規則。

基本文法：

<code>import</code> <code>re </code><code>##導入子產品</code>

<code>m </code><code>=</code> <code>re.match(</code><code>"abc"</code><code>,</code><code>"abcdefghi"</code><code>)</code>

<code>x </code><code>=</code> <code>re.match(</code><code>"abc"</code><code>,</code><code>"bcdefghi"</code><code>)</code>

<code>print</code><code>(m)</code>

<code>print</code><code>(x)</code>

<code>print</code><code>(m.group())</code>

<code><_sre.SRE_Match </code><code>object</code><code>; span</code><code>=</code><code>(</code><code>0</code><code>, </code><code>3</code><code>), match</code><code>=</code><code>'abc'</code><code>> </code><code>##object 比對上了</code>

<code>abc </code><code>## .group比對的内容</code>

比對格式：

^ : 比對字元串的開頭

$ : 比對字元串的結尾

.: 比對任意字元，除了換行符，當re.DOTALL标記被指定時，則可以比對包括換行符的任意字元。

[...]: 用來表示一組字元，單獨列出：[amk] 比對 'a','m''k'

[^...]:不在[]中的字元

re* 比對0個或多個的表達式

re+ 比對1個或多個的表達式

re? 比對0個或1個由前面的正規表達式定義的片段，非貪婪模式

re{n}

re{n,} 精确比對n個前面的表達式

a|b 比對 a 或b

(re) G比對括号内的表達式，也表示一個組

(?imx) 正規表達式包含三種可選表示 i m x 隻影響括号中的區域

(?-imx) 正規表達式關閉 imx

(?:re) 類似(...),但是不表示一個組

(?imx:re) 在括号中使用imx 可選标志

(?-imx:re) 在括号中不使用imx 可選标志

(?#...)注釋。

(?=re) 前向可定界定符

(?!re) 前向福鼎界定符

(?>re) 比對的獨立模式。

\w 比對字母數字 [A-Za-z0-9_]

\W 非字母資料 [^A-Za-z0-9]

\s 任意空白字元 [\f\n\r\t\v]

\S 非任意空白字元 [^\f\n\r\t\v]

\d 任意數字 [0-9]

\D 任意非數字 [^0-9]

\A 字元串開始

\Z 字元串結束，隻比對到換行前的結束字元串

\z 字元串結束

\G 最後比對完成的位置

\b 一個單詞邊界

\B 非單詞邊界

\n,\t 一個換行符

\1..\9 第n個分組的子表達式

\10 比對第n個分組的子表達式，如果它經比對。否則指的是八進制字元碼的表達式。

<code>re.match(pattern,string) </code><code>##從頭比對</code>

<code>re.search(pattern,string) </code><code>##比對整個字元串，直到找到一個比對</code>

<code>re.split() </code><code>##将比對到的格式當成分割點對字元串分割成清單</code>

<code>re.findall() </code><code>##找到所有要比對的字元并傳回清單格式</code>

<code>re.sub(pattern,repl,string,count,flag) </code><code>##替換比對到的字元</code>

<code>>>> m </code><code>=</code> <code>re.split(</code><code>"[0-9]"</code><code>, </code><code>"alex1rain2jack3helen rachel8"</code><code>)</code>

<code>>>> </code><code>print</code><code>(m)</code>

<code>[</code><code>'alex'</code><code>, </code><code>'rain'</code><code>, </code><code>'jack'</code><code>, </code><code>'helen rachel'</code><code>, '']</code>

<code>>>> m </code><code>=</code> <code>re.findall(</code><code>"[0-9]"</code><code>, </code><code>"alex1rain2jack3helen rachel8"</code><code>)</code>

<code>>>> m</code><code>=</code><code>re.sub(</code><code>"[0-9]"</code><code>,</code><code>"|"</code><code>, </code><code>"alex1rain2jack3helen rachel8"</code><code>,count</code><code>=</code><code>2</code> <code>)</code>

<code>alex|rain|jack3helen rachel8</code>

備注：

re.match 與re.search的差別

re.match隻比對字元串的開始，如果字元串開始不符合正規表達式，則比對失敗。

re.search比對整個字元串，直到找到一個比對。

python 比對 python

[Pp]thon Python python

rub[ye] ruby rube

[aeiou] 括号内的任意一個字母

[0-9] 任何數字

[a-z] 任何小寫字母

[A-Z] 任何大寫字母

[a-zA-Z0-9] 任何字母和數字

[^aeiou] 除了aeiou以外的所有字元

[^0-9] 除了數字外的字元

p = re.compile("^[0-9]")

m = p.match('14534Abc')

差別在于，第一種方式是提前對要比對的格式進行了編譯（對比對公式進行解析），這樣再去比對的時候就不用在編譯比對的格式，第2種簡寫是每次比對的時候都要進行一次比對公式的編譯，是以，如果你需要從一個5w行的檔案中比對出所有以數字開頭的行，建議先把正則公式進行編譯再比對，這樣速度會快點。

<code>比對手機号</code>

<code>m </code><code>=</code> <code>re.search(</code><code>"(1)([358]\d{9})"</code><code>, phone_str2) </code>

<code>比對IPV4</code>

<code>m </code><code>=</code> <code>re.search(</code><code>"\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}"</code><code>, ip_addr)</code>

<code>分組比對位址　</code>

<code>contactInfo </code><code>=</code> <code>'Oldboy School, Beijing Changping Shahe: 010-8343245'</code>

<code>match </code><code>=</code> <code>re.search(r</code><code>'(\w+), (\w+): (\S+)'</code><code>, contactInfo) </code><code>#分組</code>

<code>>>> match.group(</code><code>1</code><code>)</code>

<code> </code><code>>>> match.group(</code><code>2</code><code>)</code>

<code> </code><code>>>> match.group(</code><code>3</code><code>)</code>

<code>match </code><code>=</code> <code>re.search(r</code><code>'(?P<last>\w+), (?P<first>\w+): (?P<phone>\S+)'</code><code>, contactInfo)</code>

<code>>>> match.group(</code><code>'last'</code><code>)</code>

<code>>>> match.group(</code><code>'first'</code><code>)</code>

<code>>>> match.group(</code><code>'phone'</code><code>)</code>

<code>比對email</code>

<code>m </code><code>=</code> <code>re.search(r</code><code>"[0-9.a-z]{1,26}@[0-9.a-z]{1,20}.[0-9a-z]{0,8}.[0-9a-z]{0,8}"</code><code>, email) </code><code>##r不轉意</code>

将不規則的數組按照從小到大的順序進行排序

<code>for</code> <code>j </code><code>in</code> <code>range</code><code>(</code><code>1</code><code>,</code><code>len</code><code>(data)): </code>

<code> </code><code>for</code> <code>i </code><code>in</code> <code>range</code><code>(</code><code>len</code><code>(data)</code><code>-</code><code>j): </code><code>##-j 是因為第一次排序54,已經到最後了，不用排序了。第二次33到最後了，不用比較了。依次隻比較前面的數組。</code>

<code>print</code><code>(data)</code>

結果

[4, 10, 21, 33, 3, 8, 11, 5, 22, 2, 1, 17, 13, 6, 54]

[4, 10, 21, 3, 8, 11, 5, 22, 2, 1, 17, 13, 6, 33, 54]

[4, 10, 3, 8, 11, 5, 21, 2, 1, 17, 13, 6, 22, 33, 54]

[4, 3, 8, 10, 5, 11, 2, 1, 17, 13, 6, 21, 22, 33, 54]

[3, 4, 8, 5, 10, 2, 1, 11, 13, 6, 17, 21, 22, 33, 54]

[3, 4, 5, 8, 2, 1, 10, 11, 6, 13, 17, 21, 22, 33, 54]

[3, 4, 5, 2, 1, 8, 10, 6, 11, 13, 17, 21, 22, 33, 54]

[3, 4, 2, 1, 5, 8, 6, 10, 11, 13, 17, 21, 22, 33, 54]

[3, 2, 1, 4, 5, 6, 8, 10, 11, 13, 17, 21, 22, 33, 54]

[2, 1, 3, 4, 5, 6, 8, 10, 11, 13, 17, 21, 22, 33, 54]

[1, 2, 3, 4, 5, 6, 8, 10, 11, 13, 17, 21, 22, 33, 54]

時間複雜度

（1）時間頻度一個算法執行所耗費的時間，從理論上是不能算出來的，必須上機運作測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，隻需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

（2）時間複雜度在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間複雜度概念。一般情況下，算法中基本操作重複執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進時間複雜度，簡稱時間複雜度。

指數時間

第一個for循環的時間複雜度為Ο(n)，第二個for循環的時間複雜度為Ο(n2)，則整個算法的時間複雜度為Ο(n+n2)=Ο(n2)。

常數時間

對數時間

若算法的T(n) = O(log n)，則稱其具有對數時間

對數時間的算法是非常有效的，因為每增加一個輸入，其所需要的額外計算時間會變小。

遞歸地将字元串砍半并且輸出是這個類别函數的一個簡單例子。它需要O（log n）的時間因為每次輸出之前我們都将字元串砍半。這意味着，如果我們想增加輸出的次數，我們需要将字元串長度加倍。

線性時間　

如果一個算法的時間複雜度為O(n)，則稱這個算法具有線性時間，或O(n)時間。非正式地說，這意味着對于足夠大的輸入，運作時間增加的大小與輸入成線性關系。例如，一個計算清單所有元素的和的程式，需要的時間與清單的長度成正比。

本文轉自 295631788 51CTO部落格，原文連結：http://blog.51cto.com/hequan/1886449，如需轉載請自行聯系原作者

Python--day4--正規表達式/冒泡/時間複雜度

繼續閱讀

libsvm for python 安裝

學習軟體測試基礎測試第七天

Zeppelin 配置通路 REST APIApache Zeppelin Configuration REST API

【Torch】最簡潔logging使用指南

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Cloud Studio初體驗

使用 ctypes 進行 Python 和 C 的混合程式設計

【python】【資料處理】畫多元資料分布圖

【python】netconf協定對接管理裝置

「Python 網絡自動化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 網絡裝置

在python中建立excel并寫入

hdu7108哈希