一、算法
1、概念
算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。
算法是独立存在的一种解决问题的方法和思想。
2、算法的五大特性
输入: 算法具有0个或多个输入 输出: 算法至少有1个或多个输出 有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成 确定性：算法中的每一步都有确定的含义，不会出现二义性 可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成3、算法的复杂度： 1、衡量标准： 算法在计算机执行中所消耗的时间 算法在执行中所占用的资源的大小，如：内存空间的占用大小 算法的易理解性，易实现性 2、算法在计算机执行中消耗的时间 跟时间有关的因素： 数据输入的时间 算法编译成可执行程序的时间 计算机执行每条指令的时间 算法语句重复执行的次数
4、时间复杂度的几条基本计算规则
基本操作，即只有常数项，认为其时间复杂度为O(1) 顺序结构，时间复杂度按加法进行计算 循环结构，时间复杂度按乘法进行计算 分支结构，时间复杂度取最大值 判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度5、所消耗的时间从小到大 O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
for a in range(0, 1001):
for b in range(0, 1001):
for c in range(0, 1001):
if a**2 + b**2 == c**2 and a+b+c == 1000:
print("a, b, c: %d, %d, %d" % (a, b, c))
for a in range(0, 1001):
for b in range(0, 1001-a):
c = 1000 - a - b
if a**2 + b**2 == c**2:
print("a, b, c: %d, %d, %d" % (a, b, c))
6、常见时间复杂度之间的关系
二、 timeit模块： 可以用来测试一小段python代码的执行速度
class timeit.Timer(stmt =‘pass‘,setup=‘pass‘,timer=<timer function>)
第一个参数是要计时的语句或者函数
第二个参数是为第一个参数语句构建环境的导入语句。
timeit() 他接受一个参数为每个测试中调用被计时语句的次数，默认为一百万次，返回所消耗的秒数
# import timeit
from timeit import Timer
from timeit import timeit,repeat,default_timer
def test1():
l = []
for i in range(1000):
l.append(i)
def test2():
l = []
for i in range(1000):
l.insert(0, i)
def test3():
l = []
for i in range(1000):
l += [i]
def test4():
list1 = [x for x in range(1000)]
t4 = Timer(‘test4()‘, ‘from __main__ import test4‘)
print(‘[]:‘, t4.timeit(10000))
t1 = Timer(‘test1()‘, ‘from __main__ import test1‘)
print(‘append:‘, t1.timeit(10000))
t3 = Timer(‘test3()‘, ‘from __main__ import test3‘)
print(‘+=:‘, t3.timeit(10000))
t2 = Timer(‘test2()‘, ‘from __main__ import test2‘)
print(‘insert:‘, t2.timeit(10000))
# result = timeit(‘test1()‘,‘from __main__ import test1‘)
def del1():
x = list(range(1000))
for i in range(100):
x.pop()
def del2():
x = list(range(1000))
for i in range(100):
x.pop(0)
tt1 = timeit(‘del1()‘, ‘from __main__ import del1‘, number=10000)
tt2 = timeit(‘del2()‘, ‘from __main__ import del2‘, number=10000)
print(‘del1‘, tt1)
print(‘del2‘, tt2)
三、 数据结构
概念：
数据是一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型。如：int，float，char等。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。数据结构指数据对象中数据元素之间的关系。
Python给我们提供了很多现成的数据结构类型，这些系统自己定义好的，不需要我们自己去定义的数据结构叫做Python的内置数据结构，比如列表、元组、字典。而有些数据组织方式，Python系统里面没有直接定义，需要我们自己去定义实现这些数据的组织方式，这些数据组织方式称之为Python的扩展数据结构，比如栈，队列等。
数据是一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型。如：int，float，char等。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。数据结构指数据对象中数据元素之间的关系。
Python给我们提供了很多现成的数据结构类型，这些系统自己定义好的，不需要我们自己去定义的数据结构叫做Python的内置数据结构，比如列表、元组、字典。而有些数据组织方式，Python系统里面没有直接定义，需要我们自己去定义实现这些数据的组织方式，这些数据组织方式称之为Python的扩展数据结构，比如栈，队列等。
算法和数据结构的区别：
数据结构只是静态的描述了元素之间的关系，高效的程序需要在数据结构的基础上设计和选择算法
程序 = 数据结构+算法
总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体
四、 表结构：顺序表和链表
顺序表： 将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由他们的存储顺序自然表示
链表： 将元素存放在通过链接构造起来的一系列存储块中
顺序表的两种基本实现方式：
图a为一体式结构，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。
一体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。
图b为分离式结构，表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。
元素存储区替换：
一体式结构由于顺序表信息区与数据区连续存储在一起，所以若想更换数据区，则只能整体搬迁，即整个顺序表对象（指存储顺序表的结构信息的区域）改变了。
分离式结构若想更换数据区，只需将表信息区中的数据区链接地址更新即可，而该顺序表对象不变。
元素存储区的扩充：
扩充的两种策略
每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长。
特点：节省空间，但是扩充操作频繁，操作次数多。
每次扩充容量加倍，如每次扩充增加一倍存储空间。
特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。
Python中的list和tuple两种类型采用了顺序表的实现技术，具有前面讨论的顺序表的所有性质。
tuple是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其他方面，则与list的性质类似。
链表：
单向链表：也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
表元素域elem用来存放具体的数据。 链接域next用来存放下一个节点的位置（python中的标识） 变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。
# __author:gang
# date: 2019/8/19
class SingleNode(object):
‘‘‘单链表的节点‘‘‘
def __init__(self, item):
# _item存放数据元素
self.item = item
# _next是下一个节点的标识
self.next = None
class SingleLinkList(object):
‘‘‘单链表‘‘‘
def __init__(self):
self._head = None
def __str__(self):
return str(self._head)
def is_empty(self):
‘‘‘判断链表是否为空‘‘‘
return self._head == None
def length(self):
‘‘‘链表长度‘‘‘
# cur 初始时指向头节点
cur = self._head
count = 0
# 尾节点指向None，当未达到尾部时
while cur != None:
count += 1
cur = cur.next
return count
def travel(self):
‘‘‘遍历链表‘‘‘
cur = self._head
while cur != None:
print(cur.item)
cur = cur.next
print(‘‘)
def add(self, item):
‘‘‘头部添加元素‘‘‘
# 先创建一个保存的item值的节点
node = SingleNode(item)
# 将新节点的链接域next指向头节点，即_head指向的位置
node.next = self._head
# 将链表的头_head指向新节点
self._head = node
def append(self, item):
‘‘‘尾部添加元素‘‘‘
node = SingleNode(item)
# 先判断链表是否为空，若是空链表，则将_head指向新节点
if self.is_empty():
self._head = node
# 若不为空，则找到尾部，将尾部节点的next指向新节点
else:
cur = self._head
while cur.next != None:
cur = cur.next
cur.next = node
def insert(self, pos, item):
‘‘‘指定位置添加元素‘‘‘
# 若指定位置pos为第一个元素之前，则执行头部插入
if pos <= 0:
self.add(item)
# 若指定位置超过链表尾部，则执行尾部插入
elif pos > (self.length() - 1):
self.append(item)
# 找到指定位置
else:
node = SingleNode(item)
count = 0
# pre用来指向指定位置pos的前一个位置pos-1，初始从头结点开始移动到指定位置
pre = self._head
while count < (pos - 1):
count += 1
pre = pre.next
# 先将新节点node的next指向插入位置的节点
node.next = pre.next
# 将插入的位置的前一个节点的next指向新节点
pre.next = node
def remove(self, item):
‘‘‘删除节点‘‘‘
cur = self._head
pre = None
while cur != None:
# 找到了指定元素
if cur.item == item:
# 如果第一个就是删除的节点
if not pre:
# 将头指针指向头节点的后一个节点
self._head = cur.next
else:
# 将删除位置前一个节点的next指向删除为后一个节点
pre.next = cur.next
break
else:
# 继续向链表后移节点
pre = cur
cur = cur.next
def search(self, item):
‘‘‘链表查找节点是否存在，并返回True或者False‘‘‘
cur = self._head
while cur != None:
if cur.item == item:
return True
cur = cur.next
return False
if __name__ == ‘__main__‘:
cs = SingleLinkList()
cs.add(1)
cs.add(2)
cs.add(4)
print(‘----------‘)
cs.travel()
print(‘----------‘)
print("length:", cs.length())
cs.append(6)
cs.append(9)
cs.insert(2, 7)
print(‘----------‘)
cs.travel()
print(‘----------‘)
print("length:", cs.length())
cs.remove(4)
cs.search(2)
print(‘----------‘)
cs.travel()
print(‘----------‘)
print(cs.search(6))
View Code