JS数据结构与算法入门(一) - 数据结构与算法简介

川长思鸟来 2022-11-27 15:36 209阅读 0赞

## 1. 数据结构与算法简介 ##

**数据结构**: 计算机存储, 组织数据的方式, 就像锅碗瓢盆

**算法**: 一系列解决问题的清晰指令, 就像食谱

**两者关系**: 程序 = 数据结构 + 算法

> 将要学习的数据结构:  
> 有序的: 栈 , 队列 , 链表  
> 无序的: 集合 , 字典  
> 树 , 堆 , 图

> 将要学习的算法:  
> 链表: 遍历链表, 删除链表节点  
> 树, 图 : 深度 / 广度优先遍历  
> 数组: 冒泡 / 选择 / 插入 / 归并 / 快速排序 , 顺序 / 二分搜索

## 2. 时间复杂度和空间复杂度 ##

**时间复杂度:**  
一个函数, 用大O表示, 比如O(1), O(n), O(logN)…  
定性(大概)描述该算法的运行时间  
![时间复杂度][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDQ2NTQy_size_16_color_FFFFFF_t_70_pic_center]

O(1): 
    ------------
    let i = 0;
    i += 1
    // 每次执行该代码, 这两行代码永远只会被执行一次, 里面没有任何循环等等

O(n): 
    ------------
    for(let i = 0; i < n; i += 1) { 
    	console.log(i)
    }
    // for循环里的代码执行了n次

O(1) + O(n) = O(n): 
    ------------
    let i = 0;
    i += 1
    for(let j = 0; j < n; j += 1) { 
    	console.log(j)
    }
    // O(1)近似忽略不计

O(n) * O(n) = O(n^2): 
    ------------
    for(let i = 0; i < n; i += 1) { 
    	for(let j = 0; j < n; j += 1) { 
    		console.log(i,j)
    	}
    }

O(logN): 
    ------------
    let i = 1;
    while(i < n) { 
    	console.log(i);
    	i *= 2;
    }

--------------------

**空间复杂度:**  
一个函数, 用大O表示, 比如O(1), O(n), O(n^2)…  
算法在运行过程中临时占用存储空间大小的量度

O(1): 
    ------------
    let i = 0;
    i += 1
    // 只声明了单个变量, 单个变量占用的内存始终为1

O(n): 
    ------------
    const list = [];
    for(let i = 0; i < n; i += 1) { 
    	list.push(i)
    }
    // 声明了名为list的数组, 数组里添加了n个值,相当于占用了n个内存单元

O(n^2): 
    ------------
    const matrix = [];
    for(let i = 0; i < n; i += 1) { 
    	matrix.push([]);
    	for(let j = 0; j < n; j += 1) { 
    	matrix[i].push(j);
    	}
    }
    // 实际上是个矩阵, 前端里做栅格布局的行列, 矩阵的本质是个二维数组, 
    // 嵌套了两层的数组, 存储了n^2的变量, 所以空间复杂度是O(n^2)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4NDQ2NTQy_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/1b5420b040c340ba8d6d5c9df5357225.png