本篇文章深入解析了数据结构与算法的基础概念,涵盖复杂度分析、栈、队列与树的使用场景,并详细讲解了各种排序算法的实现与优化。

算法复杂度

算法的复杂度: 复杂度分析,事后统计法,大O表示法,时间复杂度。

时间复杂度分析

衡量算法运行速度的指标。

• 只关注循环执行次数最多的一段代码。

• 总复杂度等于最高阶项的复杂度。

• 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

  推导大O阶:

  1. 用常数1取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中,只保留最高阶项。
  3. 如果最高阶项存在切不是1,则去除与这个项相乘的常数。得到的结果就是大O阶。

  常见的时间复杂度:

  1. O(1) 常数阶
  2. O(n) 线性阶
  3. O(n²) 平方阶
  4. O(logn) 对数阶
  5. O(nlogn) 线性对数阶
  6. O(n³) 立方阶
  7. O(2ⁿ) 指数阶
  8. O(n!) 阶乘阶

  从小到大依次是:

  • O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)。

空间复杂度

衡量程序运行临时占用存储空间大小的指标。

• 算法的存储量包括:

  1. 程序本身所占空间。
  2. 输入数据所占空间。
  3. 辅助变量所占空间。

• 输入数据所占空间只取决于问题本身,和算法无关,则只需分析除输入和程序之外的辅助变量所占额外空间。

• 空间复杂度对一个算法在运行过程中临时占用的存储空间大小的量度,一般也作为问题规模n的函数,以数量级形式给出,记作: S(n)=O(g(n))。

  • g(n)的计算规则和时间复杂度一致。

    • 分析1

      public int fun(int n){
              int i,j,k,s;
              s=0;
              for (i=0;i<=n;i++)
                  for (j=0;j<=i;j++)
                      for (k=0;k<=j;k++)
                          s++;
              return(s);
          }

      由于算法中临时标量的个数与问题规模n无关,所以空间复杂度均为S(n) = O(1)。

    • 分析2

      public void fun(int a[], int n, int k) {
              int i;
              if (k == n - 1) {
                  for (i = 0; i < n; i++) {
                      //执行n次
                      System.out.println(a[i]);
                  }
              } else {
                  for (i = k; i < n; i++) {
                      //执行n-k次
                      a[i] = a[i] + i * i;
                  }
                  fun(a, n, k + 1);
              }
          }

      S(n) = O(g(1*n)),此方法属于递归算法,每次调用本身都要分配空间,fun(a,n,0)的空间复杂度为O(n)。

  注意:

  1. 空间复杂度相比时间复杂度分析要少。
  2. 对于递归算法来说,代码一般都比较简短,算法本身所占用的存储空间较少,但运行时需要占用较多的临时工作单元。
  3. 若写成非递归算法,代码一般可能比较长,算法本身占用的存储空间较多,但运行时将可能需要较少的存储单元。

递归

1. 一个问题的解可以分解为几个子问题的解。
2. 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样。
3. 存在基线/终止条件。

栈和队列

1. 栈(堆栈): 后进先出的结构,简称LIFO结构。
2. 队列: 先进先出的结构,简称FIFO结构。

树

树是n(n>=0) 个结点的有限集。n=0时称为空数。在任何一棵非空树中:

1. 有且仅有一个特定的称为跟(Root)的结点。
2. 当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一个集合本身又是一棵树,并且称为跟的子树(SubTree)。

树的度:

• 结点拥有的字段数量称为结点的度。根据各个结点的度的不同,结点可以分为:
  • 叶子结点: 度为0的结点。
  • 分支结点: 度不为0
    • 内部结点: 除了跟结点之外,分支结点也叫作内部结点。
• 树的度是树内各结点的度的最大值。

结点间关系:

• 当前结点的子树的跟称为该结点的孩子(子结点)。
• 当前结点称为其子结点的双亲【因为当前结点只有一个,所以叫做双亲结点,而不是父/母结点】。
• 同一个双亲的孩子之间互称为兄弟。
• 结点的祖先是从跟结点到当前结点所经分支上的所有结点。
• 以某结点为跟的子树中任一结点都称为该结点的子孙。

树的深度(层):

• 结点的层: 从跟结点开始,跟结点为第一层,根的孩子为第二层。若某结点为第i层,则其子树的跟就在第i+1层。
• 其双亲在同一层的结点互为堂兄弟。
• 树中结点的最大层次称为树的深度。

结点的高度=结点到叶子结点的最长路径(边数)。

结点的深度=跟结点到这个结点所经历的边的个数。

结点的层数=结点的深度+1。

树的高度==跟结点的高度。

树的有序性:

• 如果树中结点的各子树从左向右是有序的,子树间不能互换位置,则称该树为有序树,否则为无序树。

二叉树:

• 二叉树是n(n>=0)个结点的有限集合,该集合或者为空集。或者由一个根结点和两棵互不相交的,分别称为跟结点的左子树和右子树的二叉树组成。
• 特殊二叉树,斜树,满二叉树,完全二叉树。
  • 满二叉树:
    • 二叉树中除了叶子结点,每个结点的度都为2。
    • 满二叉树钟第i层的结点数为2^n-1 个。
    • 满二叉树为k的满二叉树必有2^k-1个结点,叶子数为2^k-1。
    • 满二叉树中不存在度为1的结点,每个分支点钟都有两棵深度相同的子树,切叶子结点都在最底层。
    • 具有n个结点的满二叉树的深度为log₂(n+1)。
  • 完全二叉树:
    • 二叉树中除去最后一层结点为满二叉树,且最后一层的结点依次从左到右分布。
    • 对于位置为k的结点,左子结点=2k+1,右子结点=2(k+1)。
    • 最后一个非叶结点的位置为(n/2)-1,n为数组长度。

排序

冒泡排序

一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作室重复地进行直到没有再需要交换,也就是说该数列已排序完成。这个算法的名字又来是因为元素会经由交换慢慢’浮’到数列的顶端。

1. 比较响铃的元素。如果第一个比第二个大,就交换它们两个;
2. 对每一对相邻元素做同样的工作,从开始第一队到结尾的最后一对,这样在最后的元素应该会是最大的数;
3. 针对所有的元素重复以上的步骤,除了最后一个;
4. 重复步骤1~3,直到排序完成。

选择排序

选择排序的思想其实和冒泡排序有点类似,选择排序可以看成冒泡排序的优化。

• 首先,找到数组中最大(小)的那个元素;
• 其次,将它和数组的第一个元素交换位置(如果第一个元素就是最大(小)元素那么它就和自己交换);
• 再次,在剩下的元素中找到最大(小)的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序;
• 这种方法叫做选择排序,因为它在不断地选择剩余元素之中的最大(小)者。

插入排序

• 对于未排序数据,在已排序序列中从后往前扫描,找到对应位置并插入。
• 为了给要插入的元素腾出空间,我们需要将插入位置之后的已排序元素在都向右移动一位。插入排序所需的时间取决于输入中元素的初始顺序。例如,对一个很大且其中的元素已经有序(或接近有序)的数组进行排序将会比对随机书序的数组或是逆序数组进行排序要快很多。总的来说,插入排序对于部分有序的数组十分高效,也很适合小规模数组。

快速排序

• 快速排序是对冒泡排序的一种改进,也是采用分治法的一个典型的应用。

• 首先任意选取一个数据(比如数组中的第一个数)作为关键数据,我们称为基准数,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序,也称为分区操作。

• 通过一趟快速排序将要排序的数据分隔成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

快速排序中的基准数

• 基准的选取: 最优的情况是基准值刚好取在无序区的中间,这样能够最大效率地让两边排序,同时最大地减少递归划分的次数,但是一般很难做到最优。基准的选取一般有三种方式,选取数组的第一个元素,选取数组的最后一个元素,以及选取第一个,最后一个以及中间的元素的中位数(如4 5 6 7,第一个4,最后一个7,中间的为5,这三个数的中位数为5,所以选择5作为基准)。

• Dual-Pivot快排: 两个基准数的快速排序算法,其实就是用两个基准数,把整个数组分成三份来进行快速排序,在这种新的算法下面,比经典快排从实验来看节省了10%的时间。 为了提升性能,有时我们在分隔后独立的两部分的个数小于某个数(比如15)的情况下,会采用其他排序算法,比如插入排序。

希尔排序

• 一种基于插入排序的快速的排序算法。简单插入排序对于大规模乱序数组很慢,因为元素只能一点一点地从数组的一端移动到另一端。

• 希尔排序为了加快速度简单地改进了插入排序,也称为缩小增量排序,同时该算法是冲破O(n²)的第一批算法之一。

• 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;然后缩小增量继续分组排序,随着增量逐渐减少,每组包含的关键字越来越多,当增量减至1时,整个文件恰被分成一组,再次排序,完成整个数组的排序。这个不断缩小的增量,就构成了一个增量序列。

希尔排序中的增量序列

• 从理论上说,只要一个数组是递减的,并且最后一个值是1,都可以作为增量序列使用,有没有一个步长序列,使得排序过程中所需的比较和移动次数相对较少,并且无论待排序列记录有多少,算法的时间复杂度都能渐近最佳?但是目前从数学上来说,无法证明某个序列是”最好的”。

• 常用的增量序列

  • 希尔增量序列: {N/2,(N/2)/2,..,1},其中N为原始数组的长度,这是最常用的序列,但却不是最好的。
  • Hibbard序列: {2<sup>k</sup>-1,..,3,1}。
  • Sedgewick序列: {...,109,41,19,5,1} 表达式为 94ⁱ-92ⁱ+1或者4ⁱ-3*2ⁱ+1。

归并排序

• 对于给定的一组数据,利用递归与分治技术将数据序列划分成为越来越小的半子表,在对半子表排序后,再用递归方法将排好序的半子表合并成为越来越大的有序序列。
• 为了提升性能,有时我们在半子表的个数小于某个数(比如15)的情况下,对半子表的排序采用其他排序算法,比如插入排序。
• 若将两个有序表合并成一个有序表,称为2-路归并,与之对应的还有多路归并。

堆排序

• 许多应用程序都需要处理有序的元素,但不一定要求他们全部有序,或者不一定要一次就将他们排序,很多时候,我们每次只需要操作数据中的最大元素(最小元素),那么有一种基于二叉堆的数据结构可提供支持。
• 所谓二叉堆,是一个完全二叉树的结构,同时满足堆的性质: 即子结点的键值或索引总是小于(或者大于)它的父结点。再一个二叉堆中,跟结点总是最大(或者最小)结点,这样堆我们称之为最大(小)堆。
• 堆排序算法就是抓住了这一特点,每次都取堆顶的元素,然后将剩余的元素重新调整为最大(最小)堆,以此类推,最终得到排序的序列。

计数排序

• 计数排序,基数排序,桶排序三种排序算法都利用了桶的概念,但对桶的使用方法上有差异。
• 计数排序是一个排序时不比较元素大小的排序算法。
• 计数排序对一定范围内的整数排序时候的速度非常快,一般快于其他排序算法。但计数排序局限性比较大,只限于对整数进行排序,而且待排序元素值分布较连续,跨度小的情况。
• 如果一个数组里所有元素都是整数,而且都在 0-k以内。那对于数组里每个元素来说,如果能知道数组里有多少项小于或等于该元素,就能准确给出该元素在排序后的数组的位置。 对于这个数组来说,元素5之前有8个元素小于等于5(含5本身),因此排序后5所在的位置肯定是7,只要构造一个(5+1) 大小的数组,里面存下所有对应A中每个元素之前的元素个数,就能在线性时间内完成排序。
• 实际应用中我们会同时找出数组中的max和min,主要是为了尽量节省空间。试想[1003,1001,1030,1050]这样的数据要排序,真的需要建立长度为1050+1的数组吗?我们只需要长度为1050-1003+1=48的数组(先不考虑额外+1的长度),就能囊括从最小到最大元素之间的所有元素了。
• 如果待排序数组的元素值跨度很大,比如[9999,1,2],为三个元素排序要使用9999-1+1的空间,实在是浪费。所以计数排序适用于待排序元素值分布较连续,跨度小的情况。

桶排序

• 桶排序是计数排序的升级版。

• 桶排序的工作原理: 假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序)。

  

• **在桶排序中保证元素均匀分不到每个桶尤为关键。**举个例子,有数组[0,9,4,5,8,7,6,3,2,1]要排序,它们都是10以下的数,如果还按照上面的范围[0,10)建立桶,全部的元素将进入同一个桶中,此时桶排序就失去了意义。实际情况我们很可能事先就不知道输入数据是什么,为了保证元素均匀分不到各个桶中,需要建立多少个桶,每个桶的范围是什么呢?

  其实我们可以这样: 简单点,首先限定桶的容量,再根据元素的个数来决定桶的个数。当然使用更复杂的方法也是可以的。

• 桶排序利用函数的映射关系,减少了几乎所有的比较工作。实际上,桶排序的f(k)值得计算,其作用就相当于快排中划分,已经把大量数据分隔成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。

基数排序

• 常见的数据元素一般是由若干位组成的,比如字符串由若干字符组成,整数由若干位0~9数字组成。基数排序按照从右往左的顺序,依次将每一位都当做一次关键字,然后按照该关键字对数组的元素入桶,每一轮入桶都基于上轮入桶的结果;完成所有位的入桶后,整个数组就达到有序状态。
• 比如对于数字2985,从右往左就是先以个位为关键字进行入桶,然后是十位,百位,千位,总共需要四轮。基数排序也是一种无需比较的排序算法。

位运算

• 位运算基本概念:
  • 十进制: 逢十进一
  • 二进制: 逢二进一
• 负数的表示
  • 计算机中负数的表示,是以补码的形式呈现的。
  • 
• 常用的位运算
  • 按位与 & (1&1=1,0&0=0,1&0=0)
  • 按位或 | (1|1=1,0|0=0,1|0=1)
  • 按位非 ~ (-1=0,~0=1)
  • 按位异或 ^ (1^1=0,1^0=1,0^0=0,很明显任何一个数和自己异或结果一定是0)
  • 有符号右移 >> (若正数,高位补0,负数,高位补1)
  • 有符号左移 << (低位补0)
  • 无符号右移 >>> (不论正负,高位均补0)
  • 无符号左移 <<< (低位补0)
• 运用场景
  • 网络连接(SelectionKey.java)
  • HashMap (tableSizeFor)
  • …
• 常见简单面试题
  • 取模
  • 判断奇偶数
  • 实现数字翻倍或减半
  • 交换两数

字符串处理

• 字符串匹配之BF(Bruce Force)算法
• 字符串匹配之BM(Boyer-Moore)算法
  • 坏字符: 坏字符的位置 - 模式串中的上一次出现位置
  • 好后缀: 好后缀的位置 - 模式串中的上一次出现位置
• 字符串匹配之KMP(Knuth-Morris-Pratt)算法

动态规划

动态规划定义

动态规划是运筹学的一个分支,是求解决策过程最优化的过程。

在现实生活中,有一类活动,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定,它依赖于当前面临的状态,又影响以后的发展。

所以如果一类活动过程可以分为若干个互相联系的阶段,在每一个阶段都需作出决策,每一个阶段都有若干个策略可供选择,一个阶段的策略确定以后,形成了本阶段的决策,常常影响到下一阶段的决策,从而就完全确定了一个过程的活动路线,则称它为多阶段决策问题。

当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线。在多阶段决策问题中,决策依赖于当前状态,又随即引起状态的转义,一个决策序列就是在变化的状态中产生出来的,故有”动态”的含义,称这种解决多阶段决策最优化的过程为动态规划方法。

动态规划的解题步骤

1. 确定状态转移公式,当前的状态是怎么由前面的状态变化而来的及其与之相关联的辅助的dp数组(dp table)以及下标的含义。这一步往往也是最难的,这一步想清楚了,整个动态规划的问题基本上可以说解决了一大半。一般来说,首先要确定dp数组中元素代表的意义,然后在这个意义之下,确定状态是在dp数组的元素之间如何变化的。

2. 初始化dp数组。

3. 根绝题目条件确定遍历顺序,并实现状态转移公式。

   同时在实现的过程中,可以适当的输出dp数组的值,确定自己的代码实现思路无误。

什么样的问题适合用动态规划?

多阶段决策最优解模型。

1. 最优子结构。
2. 无后效性。
3. 重复子问题。

埃氏筛和欧拉筛

• 自然数(非负整数): 从0开始: 0,1,2,3,4….。
• 素数(质数): 指在大于1的自然数中,除了1和它本身以外不再有其它因数的自然数。
• 合数: 指自然数中除了能被1和本身整除外,还能被其他数(0除外)整除的数。

埃氏筛

埃拉托色尼筛选法,简称埃氏筛法, 是针对自然数列中的自然数而实施的,用于求一定范围内的质数。也就是给定整数n,求小于n的所有质数(素数)。 埃拉托斯特尼筛法,简称埃氏筛或爱氏筛,是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数,必须把不大于根号n的所有素数的倍数剔除,剩下的就是素数。

基本思想

从2开始,将每个质数的倍数都标记成合数,以达到筛选素数的目的。

缺陷

对于一个合数,有可能被筛多次。例如 30 = 215 = 310 = 5*6……(那么如何确保每个合数只被筛选一次呢?我们只要用它的最小质因子来筛选即可)。

代码案例\

给出要筛数值的范围n,找出以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去……。

1. 首先将0,1排除:
2. 创建从2到n的连续整数列表,[2,3,4,…,n];
3. 初始化 p = 2,因为2是最小的质数;
4. 枚举所有p的倍数(2p,3p,4p,…),标记为非质数(合数);
5. 找到下一个 没有标记 且 大于p 的数。如果没有,结束运算;如果有,将该值赋予p,重复步骤4;
6. 运算结束后,剩下所有未标记的数都是找到的质数。

public static int eratosthenes(int n) {
    boolean[] isPrime = new boolean[n];// false 代表素数
    int count = 0;
    for(int i = 2;i < n; i++) {
        if(!isPrime[i]) {
            count++;
            for(int j = 2 * i;j < n;j += i) { // j就是合数的标记位
                isPrime[j] = true;
            }
        }
    }
}

欧拉筛(线性筛)

前置知识 正整数的唯一分解定理,即: 每个大于1的自然数均可写为质数的积,而且这些素因子按大小排列之后,写法仅有一种方式。

public static int eratosthenes(int n) {
    // 用来存放质数
    int[] set = new int[n + 1];
    // 用来标记合数
    boolean[] bol = new boolean[n + 1];

    int count = 0;
    for (int i = 2; i < n; i++) {
        // 如果 i 是素数 存放在 set 里
        if (!bol[i]){
            // count 统计的目前 质数的个数 正好可以用这个 count 将 质数顺序的存放在 set 集合中
            set[count] = i;
            count++;
        }

        /*
         根据 合数的定义(一个合数肯定是若干素数的乘积) 所以素数的倍数一定是合数
         所以 用 这个素数, 乘以现在已知的其他素数, 那么得到的会是一个个合数 在 bol 中标记
          */
        for (int j = 0; j < count; j++) {
            // 排除掉 超过 n 的合数
            if (i * set[j] > n) break;
            // 为合数在 bol 中做标记
            bol[i*set[j]] = true;
            if (i%set[j] == 0 ) break;
        }

    }
}

这里set[j] 就代表质数数组 2,3,5,7…。 不难发现,每一轮循环 ,对于每一个set[j] (质数),他只用了 i 值 一次,这里也是和埃氏筛法 不同的地方(埃氏筛法是 把每一个素数的 倍数在一个循环内标记完,标记出来的就不是素数), 而欧拉筛法每次只标记每个质数的i倍,标记出来的就不是素数,这是欧拉筛法的大体方向。

细细思考,这两种方法似乎是一样的 , 有点类似与 ab 和 ba 的感觉。

但是真的是这样吗?

大家都知道, 埃氏筛法会有重复标记,这是不可避免的,因为这个算法一下子标记了一个质数的 2,3,4,5,6…n倍,而就在这 2,3,4,5,6…n 这些数中,还可能分解出更小的质数,而这个更小的质数,在执行它的循环时,肯定标记过 从 2到n中的数,而到这次循环时又标记了一次,这种重复计算 极大的降低了效率,而且没有了优化的空间。

比如 12 = 26 在 埃氏筛中, 第一轮 质数2 就已经把 12 给筛走了 但是12 = 34 ,第二轮 质数 3 又筛选了一次。

而欧拉筛呢 ,他是第一轮循环 把 记录的所有质数 的 2 倍给 筛出来, 筛出来的就不是素数,第二轮把记录的所有的质数 的 3倍筛出来,筛出来的就不是素数,第三轮把记录的所有质数的4倍筛出来,筛出来的就不是素数…。 如果仅仅按照这个思路, 欧拉筛和埃氏筛一模一样,就是 ab 和 ba 的关系 。

所以欧拉筛的 精华来了。

if(i % prime[j]==0) break

先告诉你它的作用,防止重复筛选。那为什么呢?

我们来看我们一开始说的内容。 由唯一分解定理可知,任意一个自然数i必然可以 i = ab ( a为c的最小质因子这里非常重要,为什么我必须要规定 a为c的最小质因子呢? 可能 i 还可以被写成 i = cd 的形式 ,但我们只要 a * b。 我们举个例子

12 = 26 12 = 34 当对12 进行筛选的时候 ,在 12 % 2 ==0 那么直接跳出循环,3没有机会再对12进行标记。

双指针算法

双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。最常见的双指针算法有两种: 一种是,再一个序列里边,用两个指针维护一段区间;另一种是,在两个序列里边,一个指针指向其中一个序列,另外一个指针指向另一个序列,来维护某种次序。

双指针算法的核心思想(作用): 优化。

在利用双指针算法解题时,考虑原问题如何用暴力算法解出,观察是否可构成单调性,若可以,就可采用双指针算法对暴力算法进行优化,当我们采用朴素的方法即暴力枚举每一种可能的情况,时间复杂度为O(n²),而当我们使用双指针算法通过某种性质就可以将上述的O(n²)的操作优化到O(n)。

暴力算法和双指针算法区别

由于具有某种单调性,朴素算法往往能优化为双指针算法。

区别:

• 朴素算法每次在第二层遍历的时候,是会从新开始(j会回溯到初始位置),然后再遍历下去。(假设i是终点,j是起点)。
• 双指针算法: 由于具有某种单调性,每次在第二层遍历的时候,不需要回溯到初始位置(单调性),而是在满足要求的位置继续走下去或者更新掉。

public static int removeDuplicates(int[] nums) {
    if(nums.length == 0) {
        return 0;
    }
    int i = 0;
    for(int j = 1;j < nums.length; j++){
        if(nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

二分法

二分法通常又叫二分查找,一般用于查找一个有序数组中的某个值的位置或者给定的特定值的插入位置。

相比把整个数组遍历一次的O(n)复杂度,二分查找可以把复杂度降低到O(logn)。

二分法一定是建立在元素有序的前提下(或数据具有二段性),所以看到题目中出现有序数组等词时,并且要求我们查找某个值或者给一个值求插入位置,或者判断其中是否存在某个值或者利用二分思路求最大最小值等。

二分法思路很简单,无非就是每次根据中值判断,然后缩减区间到原来的一半,二分法最容易出错的地方在于边界和细节处理。

二分法的边界模板分为两种:

• 一种是左闭右闭的区间写法[left,right];while(left <= right) left 的改变为left=mid+1,right的改变为right=mid-1
• 一种是左闭右开的区间写法[left,right);while(left < right) left的改变为left=mid+1,right的改变为right=mid

x的平方根肯定在0到x之间,使用二分查找定位该数字,该数字的平方一定是最接近x的,m平方值如果大于x,则往左边找,如果小于等于x则往右边找。找到0和x的最中间的数m,如果mm > x,则m取x/2到x的中间数字,直到mm < x,m则为平方根的整数部分。

如果m * m < =x,则取0到x/2的中间值,直到两边的界限重合,找到最大的整数,则为x平方根的整数部分。时间复杂度: O(logn)。

public static int binarySearch(int x) {
    int index = -1,l = 0,r = x;
    while(l <= r) {
      int mid = l + (r - l)/2;
      if(mid * mid <= x) {
        index = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    return index;
}

牛顿迭代

牛顿迭代法是一种求方程f(x)=0近似解的一种方法。

假设我们现在得到的近似解是xi,然后我们画出在(xi,f(xi))点与曲线相切的直线,该直线与x轴相交会得到一个xi+1。根据导数与直线斜率的关系,我们可以得到: f’(xi)=(f(xi))/(xi-xi+1)。整理后得到如下递推式: xi+1=xi-f(xi)/f’(xi)。根据本递推式我们可以知道如果曲线平滑,随着迭代次数的增加,xi将愈发接近方程的解。牛顿迭代法的收敛率是平方级的,即每次迭代精度会翻倍。然而在方程有多个解时可能最后收敛的结果只会确定少数的解。

应用牛顿-拉弗森方法,要注意以下问题:

• 函数在整个定义域内最好是二阶可导的
• 起始点对求根计算影响重大,可以增加一些别的判断手段进行试错

假设平方根是i,则i和x/i必然都是x的因子,而x/i必然等于i,推导出i + x/i = 2 * i,得出i = (i + x/i) / 2。

由此得出解法,i可以任选一个值,只要上述公式成立,i必然就是x的平方根,如果不成立, (i + x/i) / 2 得出的值进行递归,直至得出正确解。

public int newton(int x) {
    if(x == 0) {
        return 0;
    }
    return (int)sqrt(x,x);
}
public double sqrt(double i, int x) {
    double res = (i + x/i)/2;
    if(res == i) {
        return i;
    } else {
        return sqrt(res, x);
    }
}