绪论

树状图总结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

graph LR
 
A[绪论] -->B(数据结构)-->C(逻辑结构)-->a(线性结构)-->d{线性表}
a-->q{栈和队列} 
a-->w{字符串}
C-->b(非线性结构)-->e{树状图}
b-->r{图结构}
B-->D(存储结构)-->t{顺序存储结构}
D-->y{链式存储结构}
A[绪论] -->c(算法)-->u(定义)
  c-->o(特性)
  c-->p(评价标准)
  c-->s(效率度量)-->f{时间复杂度}
  s-->g{空间复杂度}
  
   

在这一章中主要介绍了数据结构的基本概念和术语，以及算法和算法时间复杂度的分析方法。

• 数据结构是一门研究非数值计算程序设计中操作对象，以及这些对象之间的关系和操作对象，以及这些对象之间的关系和操作的学科。

• 数据结构包括两个方面的内容：数据的逻辑结构和存储结构。同一逻辑结构采用不同的储存方法，可以得到不同的存储结构

  1. 逻辑结构是从具体问题抽象出来的数学模型，从逻辑关系上描述数据，它与数据的存储无关。根据数据元素之间关系的不同特性，通常有四类基本逻辑结构：集合结构，线性结构，树形结构和图状结构。
  2. 存储结构是逻辑结构在计算机中的存储表示，有两类存储结构:顺序粗出结构和链式存储结构。

• 抽象数据类型是指由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象，数据对象上关系的集合，以及对数据对象的基本操作的集合。

• 算法是为了解决某类问题而规定的一个有限长的操作数列。算法具有四个特性：正确性，可读性，健壮性和高效性。

• 算法分析的两个主要方面是分析算法的时间发杂度和空间复杂度，以考察算法的时间和空间效率。一般情况下，鉴于运算空间较为充足，故将算法的时间复杂度作为分析的重点。算法执行时间的数量级称为算法的渐近时间复杂度，T(n)=O(f(n))，它表示随着问题n的增大，算法执行时间的增长率和f(n)的增长率相同，简称时间复杂度。

这一章的知识点并不多，我着重讲一下时间复杂度的相关知识

在描述算法复杂度时，经常用到O ( 1 ) , O ( n ) , O ( l o g n ) , O ( n l o g n ) 来表示对应复杂度程度, 不过目前大家默认也通过这几个方式表示空间复杂度 。

那么，O ( 1 ) , O ( n ) , O ( l o g n ) , O ( n l o g n )就可以看作既可表示算法复杂度，也可以表示空间复杂度。

大O加上（）的形式，里面其实包裹的是一个函数f ( ) , O （ f ( ) ） f(),O（f()）f(),O（f()）,指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的 n 代表输入数据的量。

如果ax=N（a>0，且a≠1），那么数x叫做以a为底N的对数，记作x=logaN，读作以a为底N的对数，其中a叫做对数的底数，N叫做真数。

比如线段树复杂度O ( l o g n + n ) ，查询修改都是O ( l o g n ) 刚学的时候简直惊为天人

1
2
3
4
5

for(int i=1;i<=n;++i)
        for(int j=1;j<=i;++j)
            for(int k=1;k<=j;++k)
                x=x+1;
1234

时间复杂度是 O(n^3)

1
2
3
4
5

int i=1;
    while(i<=n)
        i*=2;
    
1234

时间复杂度O ( l o g 2 n )−>O ( l o g n )
评测机一般能过10^8~10^9 ，根据评测机的性能以及程序的常数而定