数据结构与算法—绪论 – Python量化投资

数据结构与算法—绪论

前言




重要性





数据结构




在这里插入图片描述



概念





个人理解





相关术语



在这里插入图片描述
用户信息表users
















idnamesex
001bigsaiman
002smallsaiman
003菜虚鲲woman






users的pojo对象




class users
{ 
     //略
     int id;
     String name;
     String sex;
}
//list和woman是数据
List<users>list;//数据对象list
List<users>woman;//数据对象woman
list.add(new users(001,"bigsai","man"));//添加数据元素 一个users由(001,bigsai,man)三个数据项组成 
list.add(new users(002,"smallsai","man"));//数据元素
list.add(new users(003,"菜虚鲲","woman"));//数据元素
woman.add(list.get(2));//003,"菜虚鲲","woman"三个数据项构成的一个数据元素






三要素



  1. 逻辑结构:数据元素之间的逻辑关系。逻辑结构分为线性结构非线性结构。线性结构就是顺序表、链表之类。而非线性就是集合、树、图这些结构。
  2. 存储结构:数据结构在计算机中的表示(又称映像,也称物理结构),存储结构主要分为顺序存储链式存储索引存储散列(哈希)存储
  3. 数据的运算:施加在数据上的运算包括运算的定义实现,运算的定义基于逻辑结构,运算的实现基于存储结构。





算法分析





在这里插入图片描述




五个重要特性







算法效率的度量




通常复杂度更多描述的是一个量级程度而很少用具体数字描述。




空间复杂度




概念:是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))







时间复杂度*




概念:计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。




时间复杂度的排序:O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) <O(n!) < O(nn)




常见时间复杂度:对于时间复杂度,很多人的概念是比较模糊的。下面举例子说明一些时间复杂度。




O(1): 常数函数







O(logn): 对数函数







O(n): 线性函数







O(nlogn):







O(n2)







当然如果同样是n=10000.那么不同时间复杂度额算法执行次数、时间也不同。
























具体n执行次数
O(1)100001
O(log2n)1000014
O( n1/2)10000100
O(n)1000010000
O(nlog2n)10000140000
O(n2)10000100000000
O(n3)100001000000000000









时间复杂度计算
时间复杂度计算一般步骤







两个规则:







其他:







当然,后面会一起学习一些常见的数据结构和常见的算法,进行复杂度剖析。至于绪论,就先介绍这些,下面会先介绍线性表和递归算法。






https://www.cnblogs.com/bigsai/p/11339123.html

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论