程序 = 数据结构 + 算法
数据结构为算法提供服务,算法围绕数据结构操作
- 栈、队列、链表。
- 集合、字典。
- 树、堆、图。
- 链表:遍历链表、删除链表节点。
- 树、图:深度/广度优先遍历。
- 数组:冒泡/选择/插入/归并/快速排序、顺序/二分搜索。
一个函数,用大O表示,比如O(1)、O(n)、O(logN)...
定性描述该算法的运行时间趋势。
O(1)
:let i = 0; i += 1;
O(n)
:for (let i = 0; i < n; i+=1) { console.log(i); }
O(logN)
:let i = 1; while (i < n) { conosole.log(i); i *= 2; }
一个函数,用大O表示,比如O(1)、O(n)、O(n^2) 算法在运行过程中临时占用存储空间大小的量度。
O(1)
:let i = 0; i += 1;
O(n)
:const list = []; for (let i = 0; i < n; i += 1) { list.push(i); }
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); } }