python算法学习笔记1
python中array 是一整块单一连续的内存区域,根据索引值访问的话可以直接计算出目标元素在内存中的位置,对于链表要从头开始遍历
链表插入代价小,数值插入代价大,要移动右边所有的元素
这边的数组指动态数组
复杂度O
构建排序算法之前先对序列进行检查,如果目标已经排过序则直接返回
def sort_w_check(): n=len(seq) for i in range(n-1): if seq[i] >seq[i+1]: break else: return ....
排序的三种情况:
1.最好情况,已经排好序,线性时间
2.最坏情况
3.平均情况,期望时间
算法评估:
用timeit模块
import timeit t1=timeit.timeit("x=2+2") print(t1) t2=timeit.timeit("x=sum(range(10))") print(t2)
计算时间,但对于多次迭代时timeit会通过多次运行相关代码的方式来提高计时精度
图结构:
图的要点主要包括:
散列(hashing)可以通过python中的hash函数提供
print(hash("hello,world!")) print(hash("Hello,world!"))
python中字典类型dict就是常说的散列表,集合类型也是通过这种机制完成的,
对于散列的访问平局时间为O(1),最坏为O(n)
邻接列表及类似的结构
示意图
示意图转换为邻接集表示方法
a,b,c,d,e,f,g,h=range(8) N=[ {b,c,d,e,f}, {c,e}, {d}, {e}, {f}, {c,g,h}, {f,h}, {f,g} ]
加权的邻接列表
a,b,c,d,e,f,g,h=range(8) N=[ {b:2,c:1,d:3,e:9,f:4}, {c:4,e:3}, {d:8}, {e:7}, {f:5}, {c:2,g:2,h:2}, {f:1,h:6}, {f:9,g:8} ]
邻接集的字典表示法:
N={ 'a':set('bcdef'), 'b':set('ce'), 'c':set('d'), 'e':set('e'), 'f':set('cgh'), 'g':set('fh'), 'h':set('fg') }
树
二叉树
class Tree(object): """docstring for Tree""" def __init__(self, left,right): self.left=left self.right=right t=Tree(Tree("a","b"),Tree("c","d")) print(t.right.left)
多路搜索树
class True: def __init__(self,kids,next=None): self.kids=self.val=kids self.next=next t=Tree(Tree("a",Tree("b",Tree("c",Tree("d"))))) print(t.kids.next.next.val)
隐性平方级操作
例子
import time from random import randrange L=[randrange(10000) for i in range(1000)] t1=time.time() print(42 in L) t2=time.time() print(t2-t1) S=set(L) t3=time.time() print(42 in S) t4=time.time() print(t4-t3)
对list的搜索是线性数量级的,set的搜索是常数级的

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
len(x) 击败 x.len(),从内置函数看 Python 的设计思想
内置函数是 Python 的一大特色,用极简的语法实现很多常用的操作。 它们预先定义在内置命名空间中,开箱即用,所见即所得。Python 被公认是一种新手友好型的语言,这种说法能够成立,内置函数在其中起到了极关键的作用。 举个例子,求字符串 x 的长度,Python 的写法是 len(x) ,而且这种写法对列表、元组和字典等对象也同样适用,只需要传入对应的参数即可。len() 函数是共用的。 这是一种极简哲学的体现:Simple is better than complex。 但是,有些语言并不是这样,例如在 Java 中,字符串类有一个求长度的方法,其它类也有自己的求长度的方法,它们无法共用。每次使用时,通过类或实例来调用。 同样是求字符串长度,Python 的写法: saying = "Hello world!" print(len(saying)) # 结果:12 而在 Java 中,写法可能如下(简化起见): String saying = "Hello world!"; System.out.println(saying.length()); // 结果:12 Python ...
- 下一篇
python实现顺序查找和哈希查找算法
顺序查找 顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法,顺序查找是最简单的搜索算法,其实现如下: defsequential_search(items,item): foriinitems: ifi==item: returni else: returnFalse 适用于线性表的顺序存储结构和链式存储结构,该算法的时间复杂度为O(n)。 缺点:是当n 很大时,平均查找长度较大,效率低; 优点:是对表中数据元素的存储没有要求。另外,对于线性链表,只能进行顺序查找。 哈希查找算法 哈希查找算法,依赖哈希表这种数据结构,它是以键值对的形式存储数据,对于哈希查找算法来说,其时间复杂度为O(1),Redis数据表中也有哈希存储,储存形式是键
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- 设置Eclipse缩进为4个空格,增强代码规范
- SpringBoot2整合Redis,开启缓存,提高访问速度
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- Windows10,CentOS7,CentOS8安装Nodejs环境
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS关闭SELinux安全模块
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS7,8上快速安装Gitea,搭建Git服务器
- SpringBoot2全家桶,快速入门学习开发网站教程