记录下自己学习算法的过程,1、算法复杂度

以下仅为学习时的理解,并不完全严谨!!!
复杂度分析和大O表示法
马老师-时间复杂度-概念了解
马老师-时间复杂度-算法分析

定义

首先明确 算法是指对问题的不同解决方式,结果是相同的。

算法复杂度分两种:

  1. 时间复杂度 :运行算法时所用的时间 趋势
  2. 空间复杂度 :运行算法时额外的所用的空间(内存) 趋势
    不计算临时变量等必须的

而算法复杂度就是指这种算法所花费的时间/空间的随数据规模的变化趋势,表示方法为 Big O(大O表示法) :

T(n) = O(f(n))

大O表示法,我们在分析时间复杂度的时候往往遵循以下原则:

1、只关注循环执行次数最多的一段代码;
2、加法法则:总复杂度等于量级最大的那段代码的复杂度;
3、乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

通常考虑复杂度是建立在大数据的情况下(n较大时),计算时通常会遵循以下原则:
不考虑必须要做的操作: 必须的,没必要考虑

循环,赋初值,初始化

不考虑常数项 : 比如n>10万次时,多一次少一次已经没有太大关系了

2n-n   =   2n  = n  //2就是常数。

不考虑低次项

n²+n   =   n²

n:指代数据规模,如图中有5个数字,n=5。
O:复杂度表示法
T: 时间复杂度

常见的复杂度表示:
O(1):常量阶,无论N是多少,也只会花费1次的时间,
O(n):线性阶,根据N的变化,而复杂度也会根据N的规律增长
O(n²):平方阶,根据N的变化,而复杂度也会以N的平方次增长,对应的有 O(n³)...
O(2^n):指数阶
O(n!):阶乘阶
O(logn):对数阶
O(nlogn):线性对数阶

时间复杂度里细分起来又有最好、最坏、平均情况时间复杂度之分:

1、最好情况时间复杂度就是在最理想的情况下,执行这段代码的时间复杂度;
2、最坏情况时间复杂度就是在最糟糕的情况下,执行这段代码的时间复杂度;
3、平均情况时间复杂度顾名思义就是结合概率论分析从最好到最坏每种情况平均下来的加权平均时间复杂度
一般而言,我们关注时间复杂度就够了,只有特别严苛条件下或者复杂度相同的情况下,我们才会进一步区分最好、最坏、平均复杂度

====================================================================================================================================================================================================================================================================================================

举例说明:

如对几个数进行操作,可以用链表,也可以用数组
无标题.png

链表: 由第一个数指向的地址,找到第二个,再由第二个指向的地址找到第三个。每个位置长度是不固定的

数组:每个所占长度是相同的,因此根据想要找的个数,直接查找,不需要一个一个指向

一、上述例子的查找算法
1、链表查找算法,由于链表每次查找需要一个一个链式的指向查找,因此它的时间复杂度为O(n),是一个向上的直线,随N的增长而增长
lianbiaoselect.png

2、数组查找算法,由于数组无论长度多少,但获取一个值得时间是相同,因此为 O(1),是永远不变的直线。
szs.png

假如读取一次耗费时间为1秒,链表为: n*1 秒,而数组的为 1 秒

由此可见数组的查找算法比链表的查找算法快

====================================================================================================================================================================================================================================================================================================

计算代码的时间复杂度


代码:

let arr = [6, 8, 1, 2, 4, 7, 3, 9, 3]

// 交换排序算法
for (let i = 0; i < arr.length - 1; i++) {
  let minPos = i
  for (let j = i + 1; j < arr.length; j++) {
    minPos = arr[j] < arr[minPos] ? j : minPos
  }

  // 替换
  let x = arr[i]
  arr[i] = arr[minPos]
  arr[minPos] = x

  console.log('经过第' + i + '次替换后的数组', arr)
}

详解:
第一句:

let arr = [6, 8, 1, 2, 4, 7, 3, 9, 3]   // 不计入算法时间

第二句:

    for (let i = 0; i < arr.length - 1; i++) 
    // let i=0 // 1次
    // i<arr.length-1 // n-1次 ≈ n 次
    // i++ n-1次≈ n 次

第三句:

let minPos = i  // n-1次 ≈ n次

第四句:

for (let j = i + 1; j < arr.length; j++)  
//     let j=i+1 // n-1次
// j <arr.length // (n-1)+(n-2)...1 次,等差数列
// j++ 同上

第五句:

  minPos = arr[j] < arr[minPos] ? j : minPos  // (n-1)+(n-2)...1 次,等差数列

第六句:

     let x = arr[i]  // n-1次
  arr[i] = arr[minPos] // n-1次
  arr[minPos] = x // n-1 次

第七句:

     console.log('经过第' + i + '次替换后的数组', arr) // 不计入算法时间,最好注释

由于 n-1次 和 n次,对于大数据而言差距忽略不计,因此通常直接以n次计算。
通常算法的时间复杂度,是以循环执行次数最多的一段代码,因此只需要考虑第5句即可。

      minPos = arr[j] < arr[minPos] ? j : minPos  
    // 时间复杂度为:(n-1)+(n-2)...1 次,等差数列
    // = n²/2 - n/2 + T  ,由于 n=10000时,5000万 远大于 5万,因此忽略不计
    // ≈ n²/2

得出结果 交换算法的时间复杂度为 n²/2

=======================================

理解

复杂度通常用来评判一个算法的优劣,就是以 数据规模的趋势 来观察,而往往需要考虑算法优劣时,数据规模较大,因此很多零头都可以去掉

标签: none

添加新评论