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哈希