首先,在写这篇博客之前,需要记录一下为什么要写哈哈。现在是24/2/16距离我成为北京大学的硕士还有312天,所以这篇数据结构的笔记,也是为了我的408考研。当然,学习数据结构当然不限于只拿个卷面高分,更重要的是算法Algorithm.
1.1 研究内容
1.数据之间各种逻辑结构和物理结构,以及他们之间相应关系
2.对每种结构定义相适应的算法(在以后的Algorithm practice中,写一道算法题,首先要写出所用的Algorithm frame)
3.设计出相应的算法
4.分析算法的效率(从时间复杂度和空间复杂度两个角度判断)
1.2基本概念和术语
1.2.1数据、数据结构、数据项、数据对象、数据元素
假设有两张表,一张为人员表,一张为课程表。这两张表就是数据。单独一张表就是数据对象,人员表就是一个数据对象,每张表的每一行为数据元素,而姓名,等属性就是数据项。
1.2.2数据结构
数据结构包括逻辑结构和存储结构两个层次。是相互之间存在一种或多种特定关系的数据元素的集合(不懂)
逻辑结构(人的感官上,认为上分线性和非线性)
- 集合结构:数据元素同属于一个集合,单个数据元素之间没有任何关系!
- 线性结构:类似于线性关系,线性结构中的数据元素之间是一对一的关系。
- 树型结构:数据元素存在一对多的关系
- 图形结构(网状结构):数据元素之间是多对多关系。
存储结构(实际上计算机的内部存储结构)
- 顺序存储结构:就是把数据元素放到地址连续的存储单元里面,数据间的逻辑关系和物理关系是一致的。例如数组。
- 链式存储结构:就是把数据元素任意的放在存储单元里面,着组存储单元可以是连续的同样也可以是不连续的,根据指针找出相邻位置。
1.2.3数据类型和抽象数据类型
- 数据类型:包括整形Integer,字符型Byte,实型、数组、结构体、指针等。
- 抽象数据类型(Abstract data type ADT):类似于c++中的类。
1.3抽象数据类型的表示与实现
抽象数据类型的概念与面向对象的‘类’思想是一致的。
1.4算法和算法分析
算法+数据结构=程序
1.4.1算法的定义及特性
算法是为了解决问题而规定的操作序列。(第一步第二步)
必须满足五个特性:有穷性、确定性、可行性、输入、输出
1.4.2评价算法优劣的基本标准
正确性、可读性、健壮性、高效性
1.4.3算法的时间复杂度和空间复杂度
公司里有两个程序员,啸风和小风,二人各听老板安排写代码。最后啸风代码运行一次要花100ms,占用内存5MB,小风运行100s,占内存500MB。And then, the boss let 啸风 to go away.
Although,如果代码都没有running,how to predict it's useing times. 我们可以预估出代码基本操作执行次数。
做个比喻,场景1:一条长10寸的面包,小风每3天吃掉1寸,那么吃掉整个面包需要几天? 3×10=30天。设面包长N寸,则需要3N天。如果用一个映射法则就是函数来表达,记作T(n)=3n。
场景2:给小灰一条长16寸的面包,小灰每5天吃掉面包剩余长度的一半,第一天8寸,第二天4寸,第三天2寸...那么小灰把面包吃的只剩下1寸,需要多少天?我们取其数值和变量,就是数字16不断除以2,除几次之后剩余1,就是log以2为低,16的对数,简写为log16。因此,把面包吃的只剩下1寸,需要5*log16=5*4=20天,如果面包长n寸呢?需要5*log(n)天,记作T(n)=5logn.
场景3:给小灰一条长10寸的面包和一个鸡腿,小灰每2天吃掉一个鸡腿。那么吃掉整个鸡腿需要多少天?答案自然是2天,因为吃掉一只鸡腿自然和面包没有关系。T(n)=2。
场景4:依旧是一条10寸面包,吃掉第一个一寸需要1天,吃掉第二个1寸需要2天时间,吃掉第三个1寸需要三天...每多吃一寸,所花的时间也多一天。那么吃掉整个面包需要多少寸?答案是,从1累加到10的总和,也就是55天。如果面包长度是n寸?就是1+…+n=(1+n)*n/2=0.5n^2+0.5n。
我们把上面四个场景应用到程序设计中,刚好对应最常见的四种执行方式:
场景1:T(n)=3n,执行次数是线性的
场景2:执行次数是对数的T(n)=5logn
场景3:T(n)=2,执行次数是常量
场景4:T(n)=0.5n^2+0.5n,执行次数是一个多项式
渐进时间复杂度(asymptotic time complexity,ATC)
有了基本操作执行次数T(n),是否就可以分析和比较一段代码的运行时间了呢?答nonono。比如算法A的相对时间是T(n)=100n,算法B的相对时间是T(n)=5n^2,这两个算法谁运行时间更长取决于n的值。
若存在函数 f(n),使得当n趋近于无穷大时,T(n)/ f(n)的极限值为不等于零的常数,则称 f(n)是T(n)的同数量级函数。记作 T(n)= O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。渐进时间复杂度用大写O来表示,所以也被称为大O表示法。直白讲,时间复杂度就是把时间函数T(n)简化为一个数量级,这个数量级可以是n,n^2,n^3…。
如何推导出时间复杂度?有如下几个原则:1.如果运行时间是常数量级,用常数1表示;2.只保留时间函数中的最高阶项;3.如果最高阶项存在,则省去最高阶项前面的系数。例如T(n)=3n,简化为T(n)=O(n);T(n)=5logn,简化为T(n)=O(logn);T(n)=2,简化为T(n)=O(1);T(n)=0.5n^2+0.5n,简化为T(n)=O(n^2)。那么谁更节省时间呢?O(1)< O(logn)< O(n)< O(n^2) (看函数图像就欧克,更大的更节省时间)。
最好、最坏和平均时间复杂度
- 最好时间复杂度,指的是算法计算量可能达到的最小值。
- 最坏时间复杂度,指的是算法计算量可能达到的最大值。
- 平均时间复杂度,是指算法在所有可能情况下,按照输入实例以等概率出现时,算法计算量的加权平均值。
空间复杂度:
空间复杂度只需要分析辅助变量所占的额外空间。
空间复杂度:S(n) = O(f(n))
如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)
举例:
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)
我们再看一个代码:
int []m = new int[n];
for (i = 1; i <= n; ++i) {
j = i;
j++;
}
这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-5行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)
标签:面包,绪论,复杂度,算法,时间,数据结构,数据 From: https://www.cnblogs.com/netwxf/p/18017632