python-day20
一、算法 1、概念 算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地,当算法在处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供以后再调用。 算法是独立存在的一种解决问题的方法和思想。 2、算法的五大特性
3、算法的复杂度: ?4、时间复杂度的几条基本计算规则
5、所消耗的时间从小到大 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,c)) for a in range(0,1001-a): c = 1000 - a - b if a**2 + b**2 == c**2: print("a,%d" % (a,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为分离式结构,表对象里只保存与整个表有关的信息(即容量和元素个数),实际数据元素存放在另一个独立的元素存储区里,通过链接与基本表对象关联。 ?元素存储区替换: 一体式结构由于顺序表信息区与数据区连续存储在一起,所以若想更换数据区,则只能整体搬迁,即整个顺序表对象(指存储顺序表的结构信息的区域)改变了。 分离式结构若想更换数据区,只需将表信息区中的数据区链接地址更新即可,而该顺序表对象不变。 元素存储区的扩充: 扩充的两种策略
Python中的list和tuple两种类型采用了顺序表的实现技术,具有前面讨论的顺序表的所有性质。 tuple是不可变类型,即不变的顺序表,因此不支持改变其内部状态的任何操作,而其他方面,则与list的性质类似。 ?链表: ?单向链表:也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。
# __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)) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |