文档章节

算法从小白到大神之时间复杂度&几种排序算法探究

须臾之余
 须臾之余
发布于 08/21 23:12
字数 1720
阅读 25
收藏 0

认识时间复杂度

常数时间的操作:一个操作如果和数据量没有关系,每次都是 固定时间内完成的操作,叫做常数操作。
时间复杂度为一个算法流程中,常数操作数量的指标。常用O (读作big O)来表示。具体来说,在常数操作数量的表达式中, 只要高阶项,不要低阶项,也不要高阶项的系数,剩下的部分 如果记为f(N),那么时间复杂度为O(f(N))。
评价一个算法流程的好坏,先看时间复杂度的指标,然后再分 析不同数据样本下的实际运行时间,也就是常数项时间。

例子一

冒泡排序细节的讲解与复杂度分析
时间复杂度O(N^2),额外空间复杂度O(1)

/**
 * 冒泡排序:时间复杂度O(N^2)
 * 测试数组:  int[] arr={2,4,63,6,9};
 * 排序逻辑:
 *  1、先从数组0-arr.length-1遍历,比较[0-1,1-2,2-3...arr.length-2-arr.length-1]大的放后面,
 *  最后遍历数组,得到最后的一定是最大的元素
 *  2、再从数组0-arr.length-2遍历,比较[0-1,1-2,2-3...arr.length-3-arr.length-2]大的放后面。
 *  3、重复以上逻辑
 *  排序过程:
 *   1、[2,4,|63,6,9],[2,4,63,|6,9],[2,4,6,63,|9],[2,4,6,9,63]
 *   2、[2,4,|6,9,63],[2,4,6,|9,63],[2,4,6,9,|63]
 *   3、[2,4,|6,9,63],[2,4,6,|9,63]
 *   4、[2,4,|6,9,63]
 */
public class BubbleSort {

    public static void sort(int[] arr){
        if (arr==null ||  arr.length<2){
            return;
        }
        for (int end = arr.length-1; end>0; end--) {
            for (int i = 0; i < end; i++) {
                if (arr[i]>arr[i+1]){
                    swap(arr,i,i+1);
                }
            }
        }
    }
    //交换
    private static void swap(int[] arr, int i, int j) {
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }

    //for test
    public static void main(String[] args) {
        int[] arr={2,4,63,6,9};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

例子二

选择排序的细节讲解与复杂度分析
时间复杂度O(N^2),额外空间复杂度O(1)

/**
 * 选择排序:时间复杂度:O(N^2)
 * 测试数组:int[]arr={2,3,43,4,5,67,84,3,22,35,64};
 * 排序逻辑:
 *  1、先遍历数组(0-arr.length-1)找最小的那个元素下标:minIndex和i=0位置元素进行交换
 *  2、再遍历数组(1-arr.length-1)找最小的那个元素下标:minIndex和index=1位置元素进行交换
 *  3、重复步骤。。。。
 *  4、最后遍历完了所有元素,最后数组按照从小到大的顺序排列起来了。
 *  排序过程:
 *  1、[2,|3,43,4,5,67,84,3,22,35,64]
 *  2、[2,3,|43,4,5,67,84,3,22,35,64]
 *  3、[2,3,3,|43,4,5,67,84,22,35,64]
 *  4、[2,3,3,4,|43,5,67,84,22,35,64]
 *  5、[2,3,3,4,5,|43,67,84,22,35,64]
 *  6、[2,3,3,4,5,22,|67,84,43,35,64]
 *  7、[2,3,3,4,5,22,35,|84,43,67,64]
 *  8、[2,3,3,4,5,22,35,43,|84,67,64]
 *  9、[2,3,3,4,5,22,35,43,64,|67,84]
 *  10、[2,3,3,4,5,22,35,43,64,67,|84]
 */
public class SelectionSort {
    public static void selectionSort(int[]arr){
      if (arr==null || arr.length<2){
          return;
      }
        for (int i = 0; i < arr.length; i++) {
            int minIndex=i;
            for (int j = i+1; j < arr.length; j++) {
                minIndex=arr[j]<arr[minIndex]?j:minIndex;
            }
            if (minIndex!=i){
                swap(arr,i,minIndex);
            }
        }
    }
    private static void swap(int[] arr, int i, int j) {
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }
    public static void main(String[] args) {
        int[]arr={2,3,43,4,5,67,84,3,22,35,64};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
}

例子三

插入排序的细节讲解与复杂度分析
时间复杂度O(N^2),额外空间复杂度O(1)

/**
 * 插入排序:时间复杂度O(N^2)
 * 测试数组: int[] arr={2,4,6,7,4,333};
 * 排序逻辑:
 *  1、先0-1开始,如果前面那个元素大于后面那个元素,就进行交换,交换后前面那个元素是小的
 *  2、再从1-2比较两个元素,前一个元素小于后一个元素进行交换,再0-1比较重复步骤2
 *  3、再从2-3.。。arr.length-2-array.length-1比较.....
 *  排序过程:
 *  1、[2,4,|6,7,4,333]
 *  2、[2,4,6,|7,4,333]
 *  3、[2,4,6,7,|4,333]
 *  4、[2,4,6,4,7,|333]
 *     [2,4,4,6,7,333]
 *  5、[2,4,4,6,7,333]
 */
public class InsertSort {

    public static void insertionSort(int[] arr){
        if (arr==null || arr.length<2){
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = i-1; j >=0&&arr[j]>arr[j+1]; j--) {
                swap(arr,j,j+1);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }

    public static void main(String[] args) {
        int[] arr={2,4,6,7,4,333};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

剖析递归行为和递归行为时间复杂度的估算
一个递归行为的例子
master公式的使用

T(N) = a*T(N/b) + O(N^d)
1) log(b,a) > d -> 复杂度为O(N^log(b,a))

2) log(b,a) = d -> 复杂度为O(N^d * logN)

3) log(b,a) < d -> 复杂度为O(N^d)
补充阅读:www.gocalf.com/blog/algorithm-complexity-and-mastertheorem.html

例子四

归并排序的细节讲解与复杂度分析
时间复杂度O(N*logN),额外空间复杂度O(N)

/**
 * 二分递归归并排序:时间复杂度:O(N*logN)额外空间复杂度O(N)
 * 测试数组:  int[] arr={1,3,3,6,7,4};
 * 排序逻辑:
 *  1、[1,3,3],[6,7,4]
 *  2、[1,3],[3]  ,[6,7],[4]
 *  3、[1,3,3]  ,[4,6,7]
 *  4、[1,3,3,4,6,7]
 */
public class MergeSort {
    public static void mergeSort(int[] arr){
        if (arr==null || arr.length<2){
            return;
        }
        mergeSort(arr,0,arr.length-1);
    }

    private static void mergeSort(int[] arr, int left, int right) {
        if (left==right){
            return;
        }
        int mid =left+((right-left)>>1);
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        mergeSort(arr,left,mid,right);
    }

    private static void mergeSort(int[] arr, int left, int mid, int right) {
        int[] help=new int[right-left+1];
        int i=0;
        int p1=left;
        int p2=mid+1;
        while (p1<=mid && p2<=right){
            help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
        }
        while (p1<=mid){
            help[i++]=arr[p1++];
        }
        while (p2<=right){
            help[i++]=arr[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            //二分后每个小的数组的left
            arr[left+j]=help[j];
        }
    }

    public static void main(String[] args) {
        int[] arr={1,3,3,6,7,4};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

例子wu

小和问题和逆序对问题
小和问题
在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。求一个数组 的小和。
例子:

[1,3,4,2,5]

1左边比1小的数,没有;

3左边比3小的数,1;

4左边比4小的数,1、3;

2左边比2小的数,1;

5左边比5小的数,1、3、4、2;

所以小和为1+1+3+1+1+3+4+2=16
逆序对问题 在一个数组中,左边的数如果比右边的数大,则折两个数构成一个逆序对,请打印所有逆序 对。

/**
 * 小和问题
 */
public class SmallSum {
    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return mergeSort(arr, 0, arr.length - 1);
    }

    public static int mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + merge(arr, l, mid, r);
    }

    public static int merge(int[] arr, int l, int m, int r) {
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        int res = 0;
        while (p1 <= m && p2 <= r) {
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
        return res;
    }

    public static void main(String[] args) {
        int [] arr={1,2,3,4,5,6,7,8};
        smallSum(arr);
        System.out.println(Arrays.toString(arr));
    }
}

本文参考:牛客网

© 著作权归作者所有

须臾之余
粉丝 125
博文 68
码字总数 178724
作品 0
吉安
程序员
私信 提问
排序算法之桶排序的深入理解以及性能分析

前言 本文为算法分析系列博文之一,深入探究桶排序,分析各自环境下的性能,同时辅以性能分析示例加以佐证 实现思路与步骤 思路 设置固定空桶数 将数据放到对应的空桶中 将每个不为空的桶进行...

撒网要见鱼
2016/12/03
0
0
排序算法 之四 分类、时间/空间复杂度、如何选择

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 https://blog.csdn.net/ZCShouCSDN/article/details/90137306 写在前面   现在网上关于排序...

ZCShouEXP
05/19
0
0
《数据结构与算法之美》——冒泡排序、插入排序、选择排序

排序,是每一本数据结构的书都绕不开的重要部分。 排序的算法也是琳琅满目、五花八门。 每一个算法的背后都是智慧的结晶,思想精华的沉淀。 个人觉得排序算法没有绝对的孰优孰劣,用对了场景...

Jackie_Zheng
01/13
0
0
图书馆刘大妈除了要帮我找对象,还教我排序算法

在图书馆偶遇 快速排序算法 一次关于排序的偶遇 今天,在图书馆发生了一件事。 图书馆书架 新来的志愿者小王被安排将归还的书整理回书架,初次被委派工作的小王瞬间充满热情。然而。。。 面对...

超级数学建模
2018/03/08
0
0
PHP常见排序算法学习

题记: 常见的排序算法有:冒泡排序法,快速排序法,选择排序法,插入排序法,此处作为自己最近面试准备进行的学习笔记,同时也希望能帮到你。 需求:将一个有多个数字的数组进行从小到大的排...

moTzxx
2017/10/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CSS定位

CSS定位 relative相对定位 absolute绝对定位 fixed和sticky及zIndex relative相对定位 position特性:css position属性用于指定一个元素在文档中的定位方式。top、right、bottom、left属性则...

studywin
17分钟前
3
0
从零基础到拿到网易Java实习offer,我做对了哪些事

作为一个非科班小白,我在读研期间基本是自学Java,从一开始几乎零基础,只有一点点数据结构和Java方面的基础,到最终获得网易游戏的Java实习offer,我大概用了半年左右的时间。本文将会讲到...

Java技术江湖
昨天
5
0
程序性能checklist

程序性能checklist

Moks角木
昨天
7
0
VUE 计算属性

本文转载于:专业的前端网站▶VUE 计算属性 1、示例代码 <!DOCTYPE html><html lang="zh"> <head> <meta charset="UTF-8" /> <title>vue示例</title> </hea......

前端老手
昨天
6
0
快速搭建LNMT平台和环境部署 Tomcat详解

Tomcat部署的基本概念 1. CATALINA_HOME与CATALINA_BASE分别指什么?     CATALINA_HOME指的是Tomcat的安装目录     bin:\\Tomcat一些脚本存放目录,比如启动脚本startup.bat/start...

网络小虾米
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部