数据结构和算法基础（2）——递归、排序算法、时间复杂度

数据结构和算法基础（2）——递归、排序算法、时间复杂度 一、递归 1.定义

  程序调用自身的编程技巧称为递归（ recursion）。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
  递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

2.解决什么问题？

① 各种数学问题，例如：8皇后问题，汉诺塔，阶乘问题，迷宫问题，球和篮子问题。
② 各种算法中也会使用到递归，例如：快排，归并排序，二分查找，分治算法等。
③ 将用栈解决的问题——>递归代码比较简洁。

3.递归运用——迷宫问题 4.递归运用——八皇后问题

问题介绍 : 该问题是国际西洋棋棋手马克斯.贝瑟尔于1848年提出。在8*8格的国际象棋上摆放八个皇后，使其不能互相攻击。即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

package com.ljf.system.recursion;


public class Queen8 {
    public int maxQueen;
    public int[] array;
    public int count;

    public Queen8(int maxQueen) {
        this.maxQueen =  maxQueen;
        this.array = new int[maxQueen];
        this.count = 0;
    }
    public static void main(String[] args) {
        Queen8 queen8 = new Queen8(8);
        queen8.check(0);
        System.out.println("总共有：" + queen8.count + "种方法");
    }

    // 判断第n个皇后,当判断n皇后在第i列没问题后，就递归调用n+1皇后
    public void check(int n) {
        if (n == maxQueen) {
            for (int temp : array) {
                System.out.print(temp);
            }
            count ++;
            System.out.println();
            return;
        }

        for (int i = 0; i < maxQueen; i++) {
            array[n] = i;
            if (judge(n)) {
                check(n + 1);
            }
        }
    }

    // 判断n皇后的当前列是否和之前几个皇后冲突
    // 难点在于判断皇后是否在同一斜线上。当行数差等于列数差时就在同一直线上
    public boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            if (array[i] == array[n] || (n-i == Math.abs(array[n]-array[i]))) {
                return false;
            }
        }
        return true;
    }
}

---

二、排序算法 1.分类

主要分为内部排序和外部排序。
内部排序值将需要处理的所有数据都加载到内存中进行排序，外部排序借助外部存储进行排序，常见的内部排序有：
① 插入排序：直接插入排序和希尔排序。
② 选择排序：简单选择排序和堆排序。
③ 交换排序：冒泡排序和快速排序
④ 归并排序
⑤ 基数排序（桶排序）

2.算法复杂度

算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度。）

3.时间复杂度

时间频度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
时间复杂度
一般情况下，算法中基本 *** 作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。强调的是算法运行时间随问题规模增大时的变化。
常见的时间复杂度
① 常数阶O(1)
代码执行时，消耗不随着某个变量的增长而增长，那么无论这类代码多长，都可以用O(1)来表示它的时间复杂度。
② 对数阶O(log₂n)

int i = 1;
while(i 
在while循环里，每次将i乘以2，假设循环x次以后，i大于n了，循环结束。也就是说2的x此方等于n，那么x=log₂n。也就是运行log₂n次后，代码结束。所以时间复杂度为O(log₂n)。
 注：若a的x此方等于N（a>0且a≠1），那么x就叫做以a为底N的对数。其中a叫做底数，N叫做真数。
 ③ 线性阶O(n)
 
for(i = 1; i < n; i++) {
	j++; 
}
 
这段代码中，for循环会执行n遍。因此它消耗的时间是随着n的变化而变化的。
 ④ 线性对数阶O(nlog₂n)
 
for(i = 1; i < n; i++) {
	m = 1;
	while(i < n) {
		i = i * 2;
	}
}
 
将时间复杂度为O(log₂n)的代码循环n遍历，那么它的时间复杂度就是nO(logn),也就是O(nlog₂n)。
 
⑤ 平方阶O(n²)
 
for(int i = 1;i<=n;i++) {
	for(int j = 1; j <= n; j++) {
		w++;
	}
}
 
⑥ 立方阶O(n*n*n)、k此方阶
 和平方阶O(n²)类似，立方阶就是3层n循环。
 时间复杂度由小到大
 O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < 立方阶 < k次方阶 < 2的n此方阶段
 由此可见，我们应该避免使用指数阶的算法。
 
4.冒泡排序 
通过对待排序序列从前往后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换。每一次循环都会将大的值放到后面。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5671153.html