怎么理解时间复杂度和空间复杂度

时间复杂度和空间复杂度一般是针对算法而言，是衡量一个算法是否高效的重要标准。先纠正一个误区，时间复杂度并不是算法执行的时间，再纠正一个误区，算法不单单指冒泡排序之类的，一个循环甚至是一个判断都可以称之为算法。其实理解起来并不冲突，八大排序甚至更多的算法本质上也是通过各种循环判断来实现的。

时间复杂度：指算法语句的执行次数。O(1),O(n),O(logn),O(n2)

空间复杂度：就是一个算法在运行过程中临时占用的存储空间大小，换句话说就是被创建次数最多的变量，它被创建了多少次，那么这个算法的空间复杂度就是多少。有个规律，如果算法语句中就有创建对象，那么这个算法的时间复杂度和空间复杂度一般一致，很好理解，算法语句被执行了多少次就创建了多少对象。

数组和链表结构简单对比

数组：相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分他们的变量的集合，这个名字称为数组名，编号称为下标

数组的特性：

1.数组必须先定义固定长度，不能适应数据动态增减

2.当数据增加时，可能超出原先定义的元素个数，当数据减少时，造成内存浪费

3.数组查询比较方便，根据下标就可以直接找到元素，时间复杂度 O(1)；增加和删除比较复杂，需要移动操作数所在位置后的所有数据，时间复杂度为 O(N)

链表：是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表的特性：

1.链表动态进行存储分配，可适应数据动态增减

2.插入、删除数据比较方便,时间复杂度 O(1)；查询必须从头开始找起，十分麻烦，时间复杂度 O(N)

常见的链表:

1.单链表：通常链表每一个元素都要保存一个指向下一个元素的指针

2.双链表：每个元素既要保存到下一个元素的指针，还要保存一个上一个元素的指针

3.循环链表：在最后一个元素中下一个元素指针指向首元素

链表和数组都是在堆里分配内存

应用：

如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反， 如果需要经常插入和删除元素就需要用链表数据结构了

怎么遍历一个树

四种遍历概念

先序遍历：先访问根节点，再访问左子树，最后访问右子树。

后序遍历：先左子树，再右子树，最后根节点。

中序遍历：先左子树，再根节点，最后右子树。

层序遍历：每一层从左到右访问每一个节点。

每一个子树遍历时依然按照此时的遍历顺序。可以采用递归实现遍历。

冒泡排序（Bubble Sort）

算法描述：

● 比较相邻的元素。如果第一个比第二个大，就交换它们两个；

● 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

● 针对所有的元素重复以上的步骤，除了最后一个；

● 重复步骤 1~3，直到排序完成

如果两个元素相等，不会再交换位置，所以冒泡排序是一种稳定排序算法。

代码实现：

package com.atguigu.interview.chapter02;

/**

* @author atguigu

* @since 2019/7/22

* 冒泡排序

*/

publc class BubbleSort {

/**

* @param data 被排序的数组

*/

public static void bubbleSort( int [] data) {

int arrayLength = data.length;

for ( int i = 1 ; i < arrayLength; i++) { //第 i 次排序

for ( int j = 0 ; j < arrayLength - i; j++) { //从索引为 j 的数开始

if (data[j] > data[j + 1 ]) { //相邻元素两两对比

int temp = data[j + 1 ]; // 元素交换

data[j + 1 ] = data[j];

data[j] = temp;

}

}

System.out.println( "第" + i + "次排序：

\n" + java.util.Arrays.toString(data));

}

}

public static void main(String[] args) {

int

[] data = { 3 , 44 , 38 , 5 , 47 , 15 , 36 , 26 , 27 , 2 , 46 , 4 , 19 , 50 , 4

8 };

System.out.println( "排序之前：\n" + java.util.Arrays.toString(data));

bubbleSort(data);

System.out.println( "排序之后：\n" + java.util.Arrays.toString(data));

}

}

快速排序（Quick Sort）

算法描述：

使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

● 从数列中挑出一个元素，称为 “基准”（pivot）；

● 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

● 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

key 值的选取可以有多种形式，例如中间数或者随机数，分别会对算法的复杂度产生不同的影响。

代码实现：

package com.atguigu.interview.chapter02;

/**

* @author atguigu

* @since 2019/7/22

* 快速排序

*/

public class QuickSort {

public static void quickSort( int [] data, int low, int high) {

int i, j, temp, t;

if (low > high) {

return ;

}

i = low;

j = high;

//temp 就是基准位

temp = data[low];

System.out.println( "基准位：" + temp);

while (i < j) {

//先看右边，依次往左递减

while (temp <= data[j] && i < j) {

j--;

}

//再看左边，依次往右递增

while (temp >= data[i] && i < j) {

i++;

}

//如果满足条件则交换

if (i < j) {

System.out.println( "交换：" + data[i] + "和" + data[j]);

t = data[j];

data[j] = data[i];

data[i] = t;

System.out.println(java.util.Arrays.toString(data));

}

}

//最后将基准位与 i 和 j 相等位置的数字交换

System.out.println( "基准位" + temp + "和 i、j 相遇的位置" + data[i] + "交

换" );

data[low] = data[i];

data[i] = temp;

System.out.println(java.util.Arrays.toString(data));

//递归调用左半数组

quickSort(data, low, j - 1 );

//递归调用右半数组

quickSort(data, j + 1 , high);

}

public static void main(String[] args) {

int

[] data = { 3 , 44 , 38 , 5 , 47 , 15 , 36 , 26 , 27 , 2 , 46 , 4 , 19 , 50 , 4

8 };

System.out.println( "排序之前：\n" + java.util.Arrays.toString(data));

quickSort(data, 0 , data.length - 1 );

System.out.println( "排序之后：\n" + java.util.Arrays.toString(data));

}

}