关于java:day07数据结构与算法入门

1.1 数据的定义

在计算机科学中，数据(Data)是指所有能输出到计算机并被计算机程序解决的介质总称，是具备肯定意义的数字、字母、符号、图形，音频，视频等信息的通称。

1.2 数据元素与数据项

数据元素是数据的根本单位，也是计算机解决或者拜访的根本单位，但不是最小单位。如果咱们能够将一张表看成是数据，数据表中每一行记录都是数据元素。

数据项是数据不可再分的最小单位，一个数据元素能够由若干个数据项组成。例如一行记录中的id，创立工夫，批改工夫等。

1.3 数据类型的设计

计算机中的数据都有哪些类型呢？咱们个别能够将数据分为根本数据类型和派生数据类型(Derived Data Type)。如图所示：

2.1 数据的逻辑与存储构造

数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的汇合,是计算机中组织、存储数据的根本形式。咱们通常能够将数据结构其分为数据的逻辑构造和数据的存储构造。数据的逻辑构造形容的是数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的一种构造。数据的逻辑构造能够看作是从具体问题形象进去的计算模型。具体可分为线性构造（数组，链表，栈，队列），非线性构造（树形构造，图构造）。数据的存储构造是数据元素以及其关系在计算机存储器内的示意，是逻辑构造用计算机语言的实现。例如顺序存储构造（地位相邻）、链状存储构造（指针关联）。

2.2 数据的算法与个性

在编程畛域中，有一个对程序的说法或者说公式： “程序=数据结构+算法”。艰深的说，算法也能够了解为一个解题步骤。但从计算机程序设计的角度看，算法由一系列求解问题的指令形成，能依据标准的输出，在无限的工夫内取得无效的输入后果。算法代表了用零碎的办法来形容解决问题的一种策略机制。具备有穷性，确定性、可行性、输出（0个或多个） 、输入（1个或多个）个性，同时在设计上要求正确性、可读性、健壮性、效率与低存储量。在计算机的计算畛域中，数据结构和算法是相辅相成的，数据结构服务于算法，算法作用于数据结构。

咱们学习数据结构和

来源gao!daima.com搞$代!码网

算法这门课的一个间接指标，就是钻研如何让计算”高效”和”低耗”。这个时候就须要对计算进行复杂度剖析。复杂度剖析是数据结构和算法学习的精华。它通知咱们在设计一个零碎时，如何度量资源的耗费，运行的效率。它探讨的是一种心法，只有咱们学会了剖析问题的形式，能力见招拆招，做到无招胜有招。对于同一个问题，应用不同的算法，兴许最终失去的后果是一样的，但在过程中耗费的资源和工夫可能会有很大的区别。那么咱们应该如何去掂量不同算法之间的优劣呢？次要还是从算法所占用的「工夫」和「空间」两个维度去考量：

1）工夫维度：是指执行以后算法所耗费的工夫，咱们通常用「工夫复杂度」来形容。

2）空间维度：是指执行以后算法须要占用多少内存空间，咱们通常用「空间复杂度」来形容。

因而，评估一个算法的效率次要是看它的工夫复杂度和空间复杂度状况。然而，有的时候工夫和空间却又是”鱼和熊掌”不可兼得的。这就咱们就须要从中去取一个平衡点。

3.1 工夫复杂度剖析

咱们想要晓得一个算法的“工夫复杂度”，可能很多人首先想到的的办法就是把这个算法程序运行一遍，那么它所耗费的工夫就自然而然晓得了。这种形式能够吗？当然能够，不过它也有很多弊病。这种形式非常容易受运行环境的影响，在性能高的机器上跑进去的后果与在性能低的机器上跑的后果相差会很大。而且对测试时应用的数据规模也有很大关系。再者，并咱们在写算法的时候，还没有方法残缺的去运行呢。因而，另一种更为通用的办法就进去了： “大O符号表示法” ，即 T(n) = O(f(n))，咱们先来看个例子：

for(i=1; i<=n; ++i){
        j = i;
        j++;
}

通过“大O符号表示法”，这段代码的工夫复杂度为：O(n) ，为什么呢?在大O符号表示法中，工夫复杂度的公式是： T(n) = O( f(n) )，其中f(n) 示意每行代码执行次数之和，而O示意正比例关系，这个公式的全称是“算法的渐进工夫复杂度”。因为大O符号表示法并不是用于来实在代表算法的执行工夫的，它是用来示意代码执行工夫的增长变化趋势的。所以下面的例子中，如果n无限大的时候，常量和倍数也就意义不大了。因而间接简化为T(n) = O(n) 就能够了。

常见的工夫复杂度量级：从上至下顺次的工夫复杂度越来越大，效率越来越低

• 常数阶O(1)
• 对数阶O(logN)
• 线性阶O(n)
• 线性对数阶O(nlogN)
• 平方阶O(n²)
• 立方阶O(n³)
• K次方阶O(n^k)
• 指数阶(2^n)

常数阶O(1)

无论代码执行了多少行，只有是没有循环等简单构造，那这个代码的工夫复杂度就都是O(1)，如：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

上述代码在执行的时候，它耗费的工夫并不随着某个变量的增长而增长，那么无论这类代码有多长，即便有几万几十万行，都能够用O(1)来示意它的工夫复杂度。

线性阶O(n)

代码如下：

for(i=1; i<=n; ++i){
j = i;
j++;
}

这段代码，for循环外面的代码会执行n遍，因而它耗费的工夫是随着n的变动而变动的，因而这类代码都能够用O(n)来示意它的工夫复杂度。

对数阶O(logN)

代码如下：

int i = 1;
while(i
从下面代码能够看到，在while循环外面，每次都将 i 乘以 2，乘完之后，i 间隔 n 就越来越近了。咱们试着求解一下，假如循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n也就是说当循环 log2^n 次当前，这个代码就完结了。因而这个代码的工夫复杂度为：O(logn)

线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易了解，将工夫复杂度为O(logn)的代码循环N遍的话，那么它的工夫复杂度就是 n * O(logN)，也就是了O(nlogN)。就拿下面的代码加一点批改来举例：
for(m=1; m

平方阶O(n²)

平方阶O(n²) 就更容易了解了，如果把 O(n) 的代码再嵌套循环一遍，它的工夫复杂度就是 O(n²) 了。举例：
for(x=1; i<=n; x++){
   for(i=1; i<=n; i++){
        j = i;
        j++;
   }
}
3.2 空间复杂度剖析
既然工夫复杂度不是用来计算程序具体耗时的，那么我也应该明确，空间复杂度也不是用来计算程序理论占用的空间的。空间复杂度是对一个算法在运行过程中长期占用存储空间大小的一个量度，同样反映的是一个趋势，咱们用 S(n)=O(f(n))来定义。空间复杂度比拟罕用的有：O(1)、O(n)、O(n²)，咱们上面来看看：

空间复杂度剖析O(1)

如果算法执行所须要的长期空间不随着某个变量n的大小而变动，即此算法空间复杂度为一个常量，可示意为 O(1)，举例：
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
代码中的 i、j、m 所调配的空间都不随着解决数据量变动而变动，因而它的空间复杂度 S(n) = O(1)。

空间复杂度剖析O(n)

咱们先看一个代码：
int[] m = new int[n]
for(i=1; i<=n; ++i){
j = i;
j++;
}
这段代码中，第一行new了一个数组进去，这个数据占用的大小为n，这段代码的2-6行，尽管有循环，但没有再调配新的空间，因而，这段代码的空间复杂度次要看第一行即可，即 S(n) = O(n)。
4 总结(Summary)
4.1 重难点剖析
数据元素和数据项是什么关系？
数据的逻辑构造和存储构造定义及关系？
算法的空间复杂度和工夫复杂度剖析?
4.2 FAQ答疑
数据结构和算法要解决什么问题？（计算的高效和低耗，让计算更快，更省空间）
什么是数据的逻辑构造？（形容数据的逻辑关系）
什么是数据的存储构造? （数据在计算机中的存储实现）
为什么要进行工夫和空间的复杂度剖析？（度量算法的优劣，写出更优的代码）
工夫和空间复杂度剖析的办法?（循环次数，量级剖析等）
4.3 BUG剖析
数据元素是数据的不可再分的最小单位。谬误
数据的逻辑构造和存储构造说的是一种构造。谬误。
工夫复杂度是用来计算具体耗时的。谬误。