学习算法前你需要了解的‘大O表示法’

3,359

不管看懂了没看懂的,👬👭们都给个💗吧。写作排版不易,谢谢大家!

前言

在现实生活中,解决一个问题可以有多种方法,其中有好的方法,也有较为一般的方法。评判标准虽有不同,但总体思想是:用最小的代价获得最多的收益。

这里所说代价并不仅指金钱开销,有时也包括时间,所耗费资源等。

计算机程序也是为了解决问题而编写的。同理可知,程序有好的,也有一般的,评判标准主要有两方面:时间与空间。

人们都希望事情解决的越快越好,所以程序解决问题花费的时间一定要少。计算机资源是有限的,所以程序也要尽可能的少消耗资源。

不过很多时候不能两全其美,此时应该抓主要矛盾。在编程时,很多场合会用空间消耗的增加来换取运行时间的减少。毕竟对于我们来说,时间一般会更加重要。

那么应该怎么比较不同算法之间的优劣呢?答:应该从时间与空间两方面入手。

本文主要带你了解什么是大O表示法,但是在了解大O表示法之前,你有必要了解什么是算法。

读完本文,你将了解到:

  • 什么是算法
  • 算法设计的要求
  • 算法的好坏评定标准
  • 大O表示法

什么是算法?

算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

简而言之,计算机算法,是用计算机解决问题的方法、步骤。解决不同的问题,需要不同的算法。

比如,小学乘法算法表,九九八十一。比如,妈妈做饭脑子里出现的食谱,先炒,再炖,再小火收汁(我又饿了)。

有一个很著名的公式 “程序=数据结构+算法”

算法设计的要求

正确性

算法应当满足具体问题的需求,能够通过特定的问题测试。

可读性

算法主要是为了人的阅读与交流,其次才是机器的执行。

健壮性

当输入非法的数据时,算法也能狗适当做出反应或进行处理,而不会产生莫名奇妙的输出结果。

效率与低存储量需求

效率指算法运行的时间,执行时间短效率高;存储量需求是指算法执行过程中所需的最大存储空间

二者都与问题的规模相关,同时也要根据实际需求决择,要效率,还是要节省空间,或者折中。一般情况二者不可得兼,要么用空间换时间,要么用时间换空间。

算法的好坏评定标准

时间复杂度 :T(n)

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作 T(n)=O(f(n)) ,他表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长相同,称作算法的渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

空间复杂度 :S(n)

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。

我们这里只讨论的是时间复杂度。需要注意的是,我们分析算法的时间复杂度,并不是基于算法执行的确切时间,而是基于算法执行步骤数量。而这个执行步骤数量因不同的情况,也分最好情况、最坏情况 和 平均情况

  • 某个特定的数据集能让算法的执行情况极好,这就是最「最好情况」
  • 而另一个不同的数据会让算法的执行情况变得极差,这就是「最坏情况」
  • 不过在大多数情况下,算法的执行情况都介于这两种极端情况之间,也就是「平均情况」

我们要明白这几种情况的不同价值,这样才能帮助我们接下来了解的大O表示法

  • 最优情况:没有什么大的价值,因为它没有提供什么有用信息,反应的只是最乐观最理想的情况,没有参考价值。
  • 平均情况:是对算法的一个全面评价,因为它完整全面的反映了这个算法的性质,但从另一方面来说,这种衡量并没有什么保证,并不是每个运算都能在这种情况内完成。
  • 最坏情况:它提供了一种保证,这个保证运行时间将不会再坏了,所以一般我们所算的时间复杂度是最坏情况下的时间复杂度,做事要考虑到最坏的情况是一个道理。

因此,我们知道了,分析算法的时间复杂度的好坏,通常是根据最坏情况去分析的。

大O表示法

基本概念

定义:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性,注意它是某一个算法的时间复杂性。大O表示只是说有上界,由定义如果f(n)=O(n),那显然成立f(n)=O(n^2),它给你一个上界,但并不是上确界,但人们在表示的时候一般都习惯表示前者。

此外,一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。

“大O记法”:在这种描述中使用的基本参数是 n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order),比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时,运行时间至多将以正比于 f(n)的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能造成差异。例如,一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然,随着n足够大以后,具有较慢上升函数的算法必然工作得更快。

常见的大 O 运行时间

以下由快到慢排序。

  • O(log n),也叫对数时间,这样的算法包括二分查找
  • O(n),线性时间,包括简单查找
  • O(n*log n),包括快速排序(业界俗称快排),一种速度较快的快速排序
  • O(n^ x),包括平方时间、立方时间
  • O(2n) 指数时间
  • O(n!),包括旅行商问题的解决方案,一种非常慢的算法

O(log n)

O(log2n)表示每次循环运行之后,需要处理的数据减去一半。比如100、50、25、13。。。

对数

了解对数时间,就要先了解什么是对数,尽管对数在高一就学过,但是想必不少人都忘记了它吧(小声逼逼)。 如果你清楚什么是对数,请直接跳过这个环节。

指数是幂运算aⁿ(a≠0)中的一个参数,a为底数,n为指数,指数位于底数的右上角。

1、当指数 n=0时,

2、当指数 n>0时,,且n为整数时,

3、当指数 n<0时,

4、当指数n=2时,称为平方。

5、当指数 n=3时,称为立方。

如果

,即a的x次方等于N(a>0,且a≠1),那么数x叫做以a为底N的对数(logarithm),记作

。其中,a叫做对数的底数,N叫做真数,x叫做“以a为底N的对数”。

二分查找法

二分查找是一种算法,其输入是一个有序的元素列表。如果要查找的元素包含在列表中,二分查找返回其位置;否则返回 null

一般而言,对于包含 n 个元素的列表,用二分查找最多需要 log2 n 步,而简单查找最多需要 n 步。

我们通过 JS 来实现一下思路:

const binarySearch = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  let guess;
  while (start <= end) {
    let mid = Math.ceil((start + end) / 2);
    guess = arr[mid];
    if (guess === val) return mid;
    if (guess > val) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return -1;
}


binarySearch([1, 3, 5, 7, 9], 3);

binarySearch([1, 3, 5, 7, 9], 3);

如果我们输入一个包含100个元素的有序数组,那么我们利用二分查找,最快找到元素的步骤设为n 那么

这就是O(logn)表示法。

线性时间O(n)

o(n)表示 随着输入量的增加,时间复杂度呈线性增长。

这里以简单查找的方法举例:

function test (array,num){
  for(let i =0;i<array.length;i++){
    if(array[i] === num){
      return i
    }
  }
}

平方时间

表示的是算法的时间复杂度随着输入量的变化发生平方变化。

在js中,典型的就是双层循环

  function test(arr1,arr2,){
    arr1.map(item=>{
      arr2.map(item2=>{
        if(item2 === item1){
          return item
        }
      })
    })
  }

立方时间同理,算法的时间复杂度随着输入量的变化发生立方变化,常见的算法有三层循环。 随着循环层k的增加,算法复杂度为

指数时间

指数时间表示的算法的时间复杂度随着输入量的增加呈两倍数增加。 常见算法:选择排序

function selectionSort(arr) {
  const length = arr.length;
  for (let i = 0; i < length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1 ; j < length ; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      const temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
}

常用排序算法的时间复杂度

排序法 最差时间分析 平均时间复杂度 稳定度
冒泡排序 O(n2) O(n2) 稳定
快速排序 O(n2) O(n*log2n) 不稳定
选择排序 O(n2) O(n2) 稳定
二叉树排序 O(n2) O(n*log2n) 不一定
插入排序 O(n2) O(n2) 稳定
堆排序 O(n*log2n) O(n*log2n) 不稳定
希尔排序 O O 不稳定

以上为全部内容,谢谢您的观看和点赞。

参考文章

什么是算法?

算法图解1 - 二分查找和大O表示法

欢迎关注公众号:前端每日一博

本文使用 mdnice 排版