算法第四版

第一章. 基础

1.1 基础编程模型

本书使用了java语言的一小部分。首先学习三个基础的抽象数据类型：背包、队列、栈，使用数组、可变数组、链表实现。

性能是算法研究的核心问题，分析算法，首先对性能提出假设，建立数学模型，然后验证，并重复这个过程

算法是描述一种有限、确定、有效并适用于计算机程序来实现的解决问题的方法。算法是计算机科学的基础、是这个领域研究的核心

例如：

欧几里得算法（辗转相除法），求计算两个非负整数a，b的最大公约数 ，就是2个数都能最大整除的数，即他们最大共同的部分

比如，12和6，最大公约数是6；10和8，最大公约数是2；12和8，最大公约数是4

export function getGcd(p: number, q: number): number {
  if (q === 0)
    return p
  return getGcd(q, p % q)
}

• https://zhuanlan.zhihu.com/p/259706781

---

大部分算法都需要适当组织数据，所以就产生了数据结构，也很重要；

---

递归：方法自己调用自己

• 递归总有一个最简单的情况，第一句总是有个包含return的条件语句
• 递归调用总是尝试解决一个规模更小的子问题
• 递归调用的父问题和尝试解决的子问题不该有交集

---

1.1.10 二分查找

二分法又可以被称为二分查找，它描述了在有序集合中搜索特定值的过程。广义的二分查找是将问题的规模尽可能的缩小到原有的一半。

https://blog.csdn.net/qq_45859670/article/details/122219423

平均时间复杂度： O(logN) 最坏时间复杂度： O(logN) 最优时间复杂度： O(1)

练习

1.编写一段代码, 打印出一个M行N列二维数组的转置

  static double[][] transpose(double[][] source) {
        if (source.length == 0) return new double[0][];

        double[][] covert = new double[source[0].length][source.length];

        for (int i = 0; i < covert.length; i++) {
            for (int j = 0; j < covert[i].length; j++) {
                covert[i][j] = source[j][i];
            }
        }
        return covert;
    }