提高效率的本质：少做事情（效率＝产出／所做的事情）

2023-09-11 09:00:15 浏览数 (1)

引言

效率＝产出／所做的事情

提高效率的本质： 让计算机少做事情

在边界内做事情：从数学上可以证明N个任意随机数的排序，复杂度不可能比N乘以log（N）更低，这是数学给出的极限（边界）。

I 预备知识

1.1 计算机科学的基本做事原则：比较标准

明确一个公平的比较标准：过滤掉所有次要的因素，构建一个理想的环境（虚拟的环境）,构建可比较的、容易对比的、理想的平台。

应用场景：首先明确游戏规则，然后再开始做研究，确定基线，对比方法的优缺点。

将世界理想化的目的：找到真正的主要矛盾，过滤出那些相对次要的噪音。 将问题抽象出来，以便于抓住本质。

案例：

  1. 伽利略和牛顿在研究运动时，假设空气阻力和摩擦力可以忽略不计的，来构建理想状态。
  2. 科学家波义耳和马略特在研究气体压强和空间大小的关系时，也是先构造出理想的气体状态。
  3. 亚里士多德因为无滤除空气阻力对重力加速度的影响，得到了重物比轻物下降速度快的荒唐结论。

1.2 计算机思维的本质

翻译

把人想要做的具体事情，翻译成计算机能够懂得的程序语言。 软件开发中的关键任务就是理解并处理反映软件构成的复杂概念。

1.3 量级思维

数量级指一系列 10 的幂：数量级每差出一级，数据相差十倍左右。

个、十、百、千、万

量级是一种方便表示数量级的方式，通常使用科学计数法表示。

地球的质量是5.98x10^24千克，其中 10^24就是量级。 量级简单地讲，就是芝麻、橘子、西瓜、大象、大山、地球、太阳、银河系这样大的差别。

一个人在公司的成就：成功率x事情的量级x做事的速度

提高事情的量级需要不断学习，转变自己的角色。

从老师转型成校长，就有了量级上的突破。

对不同规模的问题要采用不同的方法

1.4 合格的工程师处理不同量级事物时的做法

  • 考虑量级的差异: 小量级和大量级的东西放在一起，前者必须被忽略掉。
  • 几个小量级的东西放在一起，远比不上一个大量级的东西。
  1. 工程师要懂得从量级上改进工程方法，这样的收获几万倍，甚至更多。
  2. 工程师要能够梳理出一个难题中各个因素在量级上的不同，知道把那些无关紧要的事情从自己的To Do List上删掉。
  3. 工程师要想着在更有影响力的事情中，参与1%。
  4. 产品经理要想怎样能让用户为你的产品多掏一倍的价钱,懂得在细节上做1%的改进，让产品的品质显得高出一个数量级。

Mac的视网膜显示屏成本比一般的显示屏价格贵不了10美元，但可以让电脑多卖一百多美元，而且用户的感觉好了不止一倍。

  1. 投资人要想办法写出最大的一张支票。
  2. 讲师要想如何当好校长。

科学家考虑的是对和错，工程师只是在现有条件下考虑好和坏的解决方案。

一个合格的软件工程师，要知道采用别人已经写好的，被长期证明运行无误的源代码，作为自己开发新产品的工具，这样才能把精力集中在解决前人未解决的问题上。

科学家告诉大家这件事的可行性，但工程师要明白怎么做。

工程师的工作：科学变成技术再变成产品

II 计算机算法

2.1 定义

计算机算法：在翻译现实世界的需求和计算机虚拟过程时，提炼出一些高效的、不断被验证过的标准流程。

将现实世界的这些问题，变成计算机可以运行的程序，中间的桥梁就是算法。 算法是一组用于解决问题或完成任务的指令或规则集合。 算法是解决问题的明确步骤，通常涉及数据操作、逻辑和控制结构。 它们是计算机程序中最基本的构建块之一，用于指导计算机执行特定的任务或操作。

2.2 模块化

制作几个非常简单，能够大量复制的模块，搭出复杂的系统。

在软件中，那些模块就是一个个的算法。

  • 将复杂的问题简单化
  • 降低成本，提高效率。

2.3 衡量算法的标准：算法复杂度

高德纳的思想

  • 在比较算法的快慢时，需要考虑数据量特别特别大，大到近乎无穷大时的情况。

计算机的发明就是为了处理大量数据的

  • 决定算法快慢的因素虽然可能很多，但是所有的因素都可以被分为两类。第一类是不随数据量变化的因素，第二类是随着数量变化的。

在研究算法时，不必考虑不变的常数，只需要看变化的因素。 算法的速度主要由后面一个因素决定，随着数量变化的因素会造成量级的差异。

  • 如果两种算法在量级上相当，在计算机科学里，就认为它们是一样好。

考虑量级的差异: 小量级和大量级的东西放在一起，前者必须被忽略掉。

高德纳删除了前面的常数因子，只保留后面的变量，他用了微积分中的一个概念——大写的O的概念，所有同等复杂度的算法，都被认为它们在"大O的概念"下是相等的。

比如冒泡排序算法的复杂度是O（N平方），插入排序也是O（N平方），属于同一个量级。

2.4 递归算法

  1. 递归的本质：自己调用自己

2）递归是一种算法，它的基本思想：将大事分解、从小事做起，步步干净利落、自顶向下设计，再自下而上回归。

对于一个复杂的问题，将原问题分解为若干个相对简单的子问题，继续下去直到简单的问题能够解决求解，也就是找到问题的出口。

3）关键因素：

  • 递归的出口
  • 递归逐步的向出口推进

4）递归的应用场景：当一次运算无法计算出结果，而且是自己调用自己，只有找到出口才拿到结果。然后返回来进行下一步的运算。

5）递归的特点：递归的时候，按照递归的深度分配全部的临时变量，栈开销很大，性能较低，要注意不能超越栈空间的大小。并且要给出一定的结束条件，否则，会造成栈溢出。6）例子：阶乘

代码语言：javascript复制
public class Recursion{
    public static void main(String[] args){
        recursion(100);
    }    
    public int recursion(int n){
        if(n=1){
            return ;
        }
        return n*recursion(n-1);
    }
}

III 提高效率的本质：少做事情

效率＝产出／所做的事情

提高效率的本质： 让计算机少做事情

在边界内做事情：从数学上可以证明N个任意随机数的排序，复杂度不可能比N乘以log（N）更低，这是数学给出的极限（边界）。

3.1 归并排序

归并排序利用了少做事情的思想，减少数据之间的相互比较，对冒泡排序进行改进。

原理：自顶向下细分，再自底向上合并。

将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将子序列间有序地合并成一个有序序列。

将一个复杂问题分解成很多简单的问题，一个个解决，最后比直接解决复杂问题要省很多时间。

  • 冒泡排序的时间复杂度为O(n^2)。
  • 归并排序的时间复杂度为 O(nlogn)。

3.2 快速排序

通常情况下最好的排序算法是"快速排序（Quicksort）"算法，它是基于比较的排序算法，其时间复杂度平均情况下是 O(nlogn)，最坏情况下是 O(n^2)，工程师们会想一些方法防止极端糟糕情况的发生。

最好的计算机算法总是有附加条件，没有绝对的最好。 常情况下复杂度是N乘以log（N），和归并排序相同。根据计算机科学的标准，它们同样好。 在工程上，快速排序算法一般情况下比归并排序快两倍。

原理：快速排序还是强调少做事情

  1. 对于一大堆无序的数字，从中随机挑选一个，这个被随机选上的数字被称为枢值，接下来，将所有要排序的数字分成两部分，第一部分是大于等于枢值的，第二部分是小于枢值的。
  2. 从上面得到的两堆数字，分别采用第一步的方法各自再找一个枢值。接下来，再把两堆数字各自分成大于等于相应枢值的数字序列，以及小于枢值的数字序列。
  3. 用同样的方法，四堆变八堆，八堆变十六堆，很快所有的数字就排好序了。

应用：

  • 快速挑选学生尖子：划出几个分数线，根据个人成绩的高低把学生分到十所学校去，第一所学校里的学生成绩最好，第十所最差，很容易地找出学习尖子。

当一个学校的学生水平都比较接近，老师教起来就容易，因此按照成绩对学生作一个初步的划分是有道理的，尤其在资源不足的情况下。

  • 高效率的社会管理办法：对每一个人作一些区分。

私营公司行政的层级如同快速排序事先划定的枢值，有了三六九等，公司才有效率可言。 刻意追求所有人一律平等，不作区分，是效率最低的办法。

IV 排序

概念：让数据有序的存储

分类：选择，冒泡，插入，归并，快速和堆

通常情况下最好的排序算法是"快速排序（Quicksort）"算法，它是基于比较的排序算法，其时间复杂度平均情况下是 O(nlogn)，最坏情况下是 O(n^2)。

最好的计算机算法总是有附加条件，没有绝对的最好。

排序的应用场景：

  • 给学生成绩排序，评奖学金或者推研
  • 电商对销售根据一些选项排序来改进自己的业务

4.1 选择排序

时间复杂度为O(n^2)。

思路：每次找到未排序部分中的最小值，然后将其放到已排序部分的最后一个位置。

固定一个位置，与其他位置作比较，满足条件交换位置。

具体实现：使用两个嵌套的循环，外层循环用来控制已排序部分的长度，内层循环用来找到未排序部分中的最小值，并将其和已排序部分的最后一个位置进行交换。

代码语言：javascript复制
public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i  ) {//控制已排序部分的长度
        int minIndex = i;
        for (int j = i   1; j < n; j  ) {//找到未排序部分中的最小值，
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        //将最小值和已排序部分的最后一个位置进行交换。
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

使用i表示第一个数据：0~arr.length-2

使用j表示后面部分的数据：i 1~arr.length-1;(j<arr.length,j ;i>j交换)

4.2 冒泡排序

冒泡排序算法的复杂度是O（N平方），插入排序也是O（N平方），属于同一个量级。

思想：从前往后比较相邻的两个元素，如果前一个元素比后一个元素大，则交换这两个元素，这样每一轮比较都会将当前未排序序列中的最大值放到序列末尾。

总是相邻的两个位置作比较，如果满足条件，交换位置。 每一次选出一个最好的，如同从水里冒出的气泡。

案例：成绩排序

第一次挑出成绩最高的同学，第二次挑出成绩次高的，如此重复。

Java 实现冒泡排序的代码：

外层循环控制排序轮数，内层循环用于比较相邻元素并交换位置。

代码语言：javascript复制
public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        int n = arr.length;
        for (int i = 0; i < n - 1; i  ) {//控制排序轮数
            for (int j = 0; j < n - i - 1; j  ) {//比较相邻元素并交换位置。
                if (arr[j] > arr[j   1]) {
                    int temp = arr[j];
                    arr[j] = arr[j   1];
                    arr[j   1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 2, 4};
        bubbleSort(arr);
        for (int i : arr) {
            System.out.print(i   " ");
        }
    }
}

4.3 插入排序

基本思想：将待排序的数据分成两部分，已排序部分和未排序部分。每次从未排序部分取出一个元素，将其插入到已排序部分中的合适位置，直到所有元素都被插入到已排序部分中。

每一次要找到合适的位置插入。

案例：成绩排序

先将成绩单上第一个同学的名字和成绩写到旁边一张白纸的中央， 如果第二个同学成绩比他高，就写到第一个同学的上方，如果比他低，就写到下方。 看到第三个同学的成绩后，根据他的成绩与前两个同学成绩的比较，插入到相应的位置。比如他的成绩正好在两个同学之间，就在旁边那张排序的纸上，把他的名字插入到前两个人之间。

代码示例： Java 实现插入排序

  • i代表需要插入的元素的位置：1~arr.lenght-1
  • j代表前一部分每一个元素的位置： 0~i-1
代码语言：javascript复制
//该方法接受一个整型数组作为参数，对其进行插入排序。
//在方法中，变量 n 存储数组的长度。
//接着使用一个循环，从数组的第二个元素开始遍历，将其插入到已排序部分中。
//变量 key 存储当前要插入的元素，变量 j 存储已排序部分中最后一个元素的下标。使用一个 while 循环，将已排序部分中大于 key 的元素后移一位，直到找到 key 的插入位置。最后将 key 插入到数组中。

public static void insertionSort(int[] arr) {
    int n = arr.length;//存储数组的长度
    for (int i = 1; i < n; i  ) {//从数组的第二个元素开始遍历，将其插入到已排序部分中
        int key = arr[i];// 存储当前要插入的元素
        int j = i - 1;//存储已排序部分中最后一个元素的下标
        while (j >= 0 && arr[j] > key) {//将已排序部分中大于 key 的元素后移一位，直到找到 key 的插入位置
            arr[j   1] = arr[j];
            j--;
        }
        arr[j   1] = key;//将 key 插入到数组中
    }
}

4.4 归并排序

归并排序利用了少做事情的思想，对冒泡排序进行改进，时间复杂度为 O(nlogn)。

思想：将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将子序列间有序地合并成一个有序序列。

具体实现分为两步：分割序列 合并序列

分割序列：将待排序序列不断分割成两个子序列，直到每个子序列只有一个元素为止。 合并序列：将相邻的两个子序列有序地合并成一个有序序列，直到最终序列有序为止。

代码实现归并排序

代码语言：javascript复制
//mergeSort 方法对序列进行分割，merge 方法对分割后的序列进行合并。其中，temp 数组用于存储合并后的序列，i 和 j 分别表示左右子序列的起始位置，k 表示 temp 数组的当前位置。



public class MergeSort {
//对序列进行分割
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left   right) / 2;
            // 分割序列
            mergeSort(arr, left, mid);
            mergeSort(arr, mid   1, right);
            // 合并序列
            merge(arr, left, mid, right);
        }
    }
//对分割后的序列进行合并
    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left   1];//temp 数组用于存储合并后的序列
        int i = left, j = mid   1, k = 0;//i 和 j 分别表示左右子序列的起始位置，k 表示 temp 数组的当前位置。
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[k  ] = arr[i  ];
            } else {
                temp[k  ] = arr[j  ];
            }
        }
        while (i <= mid) {
            temp[k  ] = arr[i  ];
        }
        while (j <= right) {
            temp[k  ] = arr[j  ];
        }
        for (int p = 0; p < temp.length; p  ) {
            arr[left   p] = temp[p];
        }
    }

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

4.5 快速排序（常用的排序算法）

基于比较的排序算法，其时间复杂度为平均情况下的 O(nlogn)，最坏情况下的 O(n^2)。

Java 实现快速排序的代码：

sort 是快速排序的主要函数，它调用了 quickSort 函数来实现排序。 quickSort 函数使用了一个 pivot 元素来将数组分为两个子数组，并递归对它们进行排序。 在每一次递归中，首先选择一个 pivot 元素，然后从数组两端开始扫描，找到两个元素，一个在左边，一个在右边，它们本来应该在 pivot 的左边和右边，但由于位置不正确，需要交换它们。一直重复这个过程，直到最后子数组只有一个元素为止。

代码语言：javascript复制
public class QuickSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = arr[(left   right) / 2];//用了 `pivot` 元素来将数组分为两个子数组，并递归对它们进行排序
        int i = left;
        int j = right;
        while (i <= j) {
            while (arr[i] < pivot) {
                i  ;
            }
            while (arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(arr, i, j);
                i  ;
                j--;
            }
        }
        quickSort(arr, left, j);
        quickSort(arr, i, right);
    }

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

4.6 Java 堆排序

思想：基于二叉堆的排序算法，它利用了堆的性质来进行排序。

堆排序分为两个主要步骤：建堆和排序。

  • 建堆的过程是将待排序的数组构建成一个二叉堆，通常使用最大堆（大顶堆）来进行排序。
  • 排序的过程是不断地从堆顶取出最大值（根节点），将其与堆中最后一个元素交换，然后重新调整堆，使得剩余元素仍满足堆的性质。
代码语言：javascript复制
//定义了一个 heapSort 方法，它接受一个整数数组作为参数，然后对数组进行堆排序。
//在排序过程中，首先通过 heapify 方法建立一个最大堆。
//然后，从数组末尾开始，将最大值（根节点）与当前位置的元素交换，接着调整堆，使得交换后的剩余元素仍满足堆的性质。
//最终，通过不断重复这个过程，得到一个有序的数组。

public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 建堆（构造最大堆）
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 排序
        for (int i = n - 1; i > 0; i--) {
            // 将当前最大值（根节点）与最后一个元素交换
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 调整堆，使剩余元素仍满足最大堆性质
            heapify(arr, i, 0);
        }
    }

    public static void heapify(int[] arr, int n, int i) {
        int largest = i;  // 初始化最大值为当前节点
        int left = 2 * i   1;  // 左子节点索引
        int right = 2 * i   2;  // 右子节点索引

        // 如果左子节点大于最大值节点，更新最大值节点
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        // 如果右子节点大于最大值节点，更新最大值节点
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // 如果最大值节点不是当前节点，交换节点并递归调整堆
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;

            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 2, 4};
        heapSort(arr);
        for (int i : arr) {
            System.out.print(i   " ");
        }
    }
}
递归 排序 数组 算法 效率

0 人点赞