博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[-算法篇-] 开篇前言
阅读量:6861 次
发布时间:2019-06-26

本文共 7382 字,大约阅读时间需要 24 分钟。

零、前言

[1].从冒泡排序和快速排序引入算法[2].时间复杂度的引入[3].空间复杂度的引入[4].数据结构和算法之间的杂谈复制代码
关于程序的执行
输入: 原生可用数据 = 数据获取 + 数据解析处理:逻辑加工(算法核心)输出:获得预期数据拿一个排序算法来说:[输入原始杂乱数据,通过逻辑加工,生成预期有序数据]复制代码

一、从冒泡排序和快速排序开始说起

100W个随机数,存储到文件中,使用时解析数据形成int数组

问: 为什么要存到文件里,直接在内存里不就行了吗?
---- 数据固化之后,保证原始数据不变且容易查看和再加工

  • 排序之前的前3000个

  • 排序之前的前3000个


1、数据准备
1.1原始数据的生成

数据的来源可以多种多样,这里用最简单的方式生成大批量数据,随机100W个0~100W的数字

public class NumMaker {    public static void main(String[] args) throws IOException {        String path = "J:\\sf\\data\\num.txt";        int bound = 100 * 10000;        initData(path, bound);    }    /**     * 初始化数据     *     * @param path  文件路径     * @param bound 数据个数     * @throws IOException      */    private static void initData(String path, int bound) throws IOException {        Random random = new Random();        FileHelper.mkFile(path);        StringBuilder sb = new StringBuilder();        for (int i = 0; i < bound; i++) {            sb.append(random.nextInt(bound));            if (i != bound - 1) {                sb.append(",");            }        }        FileWriter writer = new FileWriter(path);        writer.write(sb.toString());        writer.close();    }}/** * 创建文件 * @param path 文件路径 * @return 文件是否被创建 */public static boolean mkFile(String path) {    boolean success = true;    File file = new File(path);//1.创建文件对象    if (file.exists()) {//2.判断文件是否存在        return false;//已存在则返回    }    File parent = file.getParentFile();//3.获取父文件    if (!parent.exists()) {        if (!parent.mkdirs()) {//4.创建父文件            return false;        }    }    try {        success = file.createNewFile();//5.创建文件    } catch (IOException e) {        success = false;        e.printStackTrace();    }    return success;}复制代码

1.2.数据解析

/** * 解析原始数据,得到int数组 * @param path 路径 * @return int数组 */private static int[] parseData(String path) throws IOException {    FileReader reader = new FileReader(path);    StringBuilder sb = new StringBuilder();    int len = 0;    char[] buf = new char[1024];    while ((len = reader.read(buf)) != -1) {        sb.append(new String(buf, 0, len));    }    String[] data = sb.toString().split(",");    //String数组转int    int[] ints = new int[data.length];    for (int i = 0; i < ints.length; i++) {        ints[i] = Integer.parseInt(data[i]);    }    return ints;}复制代码

2.冒泡排序与快速排序
/** * 冒泡排序 * @param arr 数组 * @param n 个数 */private static void bubbleSort(int arr[], int n) {    int i, j, t;    // 要遍历的次数,第i趟排序    for (i = 1; i < n - 1; i++) {        for (j = 0; j < n - 1; j++) {            // 若前者大于后者,则交换            if (arr[j] > arr[j + 1]) {                t = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = t;            }        }    }}/** * 快速排序 * * @param arr   数组 * @param start 起点 * @param end   重点 */private static void fastSort(int[] arr, int start, int end) {    int i, j, key;    if (start >= end) {        return;    }    i = start + 1;    j = end;    key = arr[start];//基准位    while (i < j) {        while (key <= arr[j] && i < j) j--; //←--        while (key >= arr[i] && i < j) i++; //--→        if (i < j) {//交换            int t = arr[j];            arr[j] = arr[i];            arr[i] = t;        }    }    arr[start] = arr[i];//交换基准位    arr[i] = key;    fastSort(arr, start, j - 1);//左半    fastSort(arr, j + 1, end);//右半}复制代码

3.数据输出(固化到文件)
//使用冒泡排序// System.out.println("bubbleSort开始-----------------------");// long start = System.currentTimeMillis();// bubbleSort(data, data.length);// long end = System.currentTimeMillis();// System.out.println("bubbleSort耗时:" + (end - start) / 1000.f + "秒");//使用快速排序System.out.println("fastSort开始-----------------------");long start = System.currentTimeMillis();fastSort(data, 0, data.length-1);long end = System.currentTimeMillis();System.out.println("fastSort耗时:" + (end - start) / 1000.f + "秒");String path_sort = "J:\\sf\\data\\num_sort.txt";saveInts(data, path_sort);//将结果保存到文件复制代码

4.简单的散点图绘制

用python的matplotlib,就这么简单

由于100W条数据太多,渲染太慢,就算渲染出来也一片糊,这里取前3000个感受一下。

import matplotlib.pyplot as pltdef init_data():    data_raw = open("J:\\sf\\data\\num_raw.txt").readline()    data = data_raw.split(",")    data = list(map(int, data))  # 将字符型列表转为int型    for i in range(2000, 3000):  # 查看的数据索引范围        plt.scatter(i, data[i], alpha=0.6)if __name__ == '__main__':    init_data()    plt.show()  # 显示所画的图复制代码

5.关于排序算法

冒泡排序和使用快速

冒泡排序排列:fastSort开始-----------------------等了一个小时都没排出来,算了,不等了,我就点了暂停...使用快速排序:fastSort开始-----------------------fastSort耗时:0.216秒 这TM是"愚公移山"和"沉香劈山"的差距啊...,短短的几行代码,都是智慧的结晶。等两个小时都排不出来和 0.216秒 完成任务,这就是算法带来的价值复制代码

这时你也许会问:两种排序的差距为何如此巨大,且听下面细细分解。


二、时间复杂度(简述):描述算法运行时间和输入数据之间的关系

1.一亿次加法+赋值的耗时:
System.out.println("fastSort开始-----------------------");long start = System.nanoTime();for (int i = 0; i < 100000000; i++) {    int a = 1 + i;}long end = System.nanoTime();System.out.println("fastSort耗时:" + (end - start) + "纳秒");结果在: 6324942 纳秒左右 即:6.324942 ms (1 ns = 100 0000 ms) 复制代码

2.关于计算机常识

CPU的主频:即CPU内核工作的时钟频率,例如我的笔记本是2.20GHz频率(Hz):描述周期性循环信号(包括脉冲信号)在单位时间内所出现的脉冲数量1GHz=1000MHz,1MHz=1000kHz,1kHz=1000Hz2.20GHz = 2200 MHz = 2200 000 kHz = 2200 000 000 Hz 即22亿Hz即一秒钟内CPU脉冲震荡次数为 22 亿次 ,由于执行某指令需要多个时钟周期但由于不同指令所需的周期数是不定的,具体1s能执行多少次指令很难量化于是一个算法的时间复杂度应运而生,其中理想化了一个计算模型:1.标准的简单指令系统:运算与赋值等2.模型机处理简单指令的都恰好花费1个时间单位复制代码

3.冒泡算法的时间复杂度
/** * 冒泡排序 * @param arr 数组 * @param n 个数 */private static void bubbleSort(int arr[], int n) {    int i, j, t;    // 要遍历的次数,第i趟排序    for (i = 1; i < n - 1; i++) {        for (j = 0; j < n - 1; j++) {            // 若前者大于后者,则交换            if (arr[j] > arr[j + 1]) {                t = arr[j];                arr[j] = arr[j + 1];                arr[j + 1] = t;            }        }    }}其外层循环执行 N - 1 次。内层循环最多的时候执行N次,最少的时候执行1次,平均执行 (N+1)/2 次。所以循环体内的[交换逻辑]约执行:(N - 1)(N + 1) / 2 = (N^2 -1)/2 次。按照计算复杂度的原则,去掉常数,去掉最高项系数,其复杂度为O(N^2)。也就是说100W条数据, 最多要执行 100W*100W(即100亿) 次交换逻辑 测试了一下一次交换逻辑平均耗时500纳秒左右所以总耗时: 500 * 100亿 ms = 5000 秒 = 1.3888889 时复制代码


4.快速排序的分析

我在交换时放了一个count计数,最终:count = 3919355 远比冒泡排序要少

/** * 快速排序 * * @param arr   数组 * @param start 起点 * @param end   重点 */private static void fastSort(int[] arr, int start, int end) {    int i, j, key;    if (start >= end) {        return;    }    i = start + 1;    j = end;    key = arr[start];//基准位    while (i < j) {        while (key <= arr[j] && i < j) j--; //←--        while (key >= arr[i] && i < j) i++; //--→        if (i < j) {//交换            int t = arr[j];            arr[j] = arr[i];            arr[i] = t;        }    }    arr[start] = arr[i];//交换基准位    arr[i] = key;    fastSort(arr, start, j - 1);//左半    fastSort(arr, j + 1, end);//右半}快速排序时间复杂度是:nlogn , 即平均执行 100W*log100W ≈ 20 * 100W  = 2000W 次 ,快速排序时间复杂度的计算这里暂时就不分析了,后面会有专题 复制代码

三、空间复杂度(简述):描述算法消耗临时空间和输入数据之间的关系

暂略


四、散扯

1.数据结构与算法分析
数据结构离不开算法分析,结构本身是对现实中问题的抽象,算法使之呈现  算法虽然可以独立于结构存在,但数据结构可以使之绚丽多彩,变幻莫测  复制代码

2.数据与结构
其实我更愿意将数据和结构分开来说:数据是应用程序存在和生存必不可少的部分,就像化学元素之于生物而结构给了数据更好的承载体,复杂而优秀的结构有利于物种的存在与支配资源,就像人类之于酵母菌 一个生物的DNA结构决定了它的形貌,一个生物的骨架决定了它有何优势,如何生存。在我眼中结构是自然的,纯正的。而数据会附和与结构形成一种美妙的状态复制代码

3.算法与分析
坦白说,我的算法很渣,但我喜欢分析和计算,我一直觉得,算法和计算是两个不同的概念计算是数学的,会依赖数学公式,特别是一些图形相、绘制相关的计算但算法给人感觉很深沉或说深奥,而且条条大路通罗马,需要分析优劣算法最令我失落的是:我可以一字不落背下它,可以debug一步一步理解它,可以画图去演示它,但我不想到它为何存在,第一个设计它的人是怎么想的,这种感觉让我很难受。复制代码

4.杂谈
一开始接触队列时感觉so easy,不就是入队,出队,查看队首吗?链表不就是一个一个接起来,这有什么难的?你知道一件事物是什么和你能运用它创造价值是天壤之别当看到阻塞队列和信息队列,感觉自己是多么无知也许可以硬记背出红黑树的特点,甚至实现的细节,如果不去思考一个算法为什么存在,那它也许只是你脑子里的一团干草,没有养分而且占用空间。因为算法中的巧妙之处太多太多,一深究就StackOver(栈溢出),导致我一直避让着算法,但是:复制代码

5.如果把一个程序比作人 :
结构是支撑人体存在的骨架数据是附着在骨架上的血液与肉体算法是支配骨架和血肉的灵魂复制代码

转载地址:http://dsayl.baihongyu.com/

你可能感兴趣的文章
Spring AOP根据JdbcTemplate方法名动态设置数据源
查看>>
sublime3学习笔记2:编辑
查看>>
字节缓冲[转载]
查看>>
又做梦了..
查看>>
抽象代数的研究对象辨析
查看>>
我的友情链接
查看>>
英特尔至强系列处理器发布计划曝光
查看>>
Java集合框架总结(4)——List接口的使用
查看>>
Java几款性能分析工具的对比
查看>>
Azure手把手系列 1:微软中国公有云概述
查看>>
Nagios设置飞信报警
查看>>
php配置手册
查看>>
使用 mysqldump 迁移 MySQL 数据-企业实战
查看>>
java 学习笔记6-集合
查看>>
H3C ACL应用到接口的几种命令
查看>>
"岛主" 同学给我出的算法题
查看>>
GDI+ 学习记录(18): 闭合曲线 - ClosedCurve
查看>>
JAVA注解Annotation
查看>>
mysql数据库密码的恢复与重设
查看>>
Android SQLite使用
查看>>