数据结构与算法 概念
数据结构
算法
-
算法：对特定问题的求解步骤，是指令的有限序列，包含5个重要的特征 有穷性：一个算法总是在执行有穷步之后结束 确定性：每条指令必须有确切的含有且只有一条执行路径，即对于相同的输入只能得到相同的输出 可行性：一个算法是能行的，即算法中描述的操作都是可以通过已实现的基本运算执行有限次来实现的 输入：一个算法有零个或多个输入 输出：一个算法有一个或多个输出 算法分析 时间复杂度：程序允许时间（t）与数据规模（n）构成的函数 空间复杂度：程序所需存储空间的量度 输入数据所占 程序本身所占 辅助变量所占
时间复杂度
-
O(1) 常数级：数组下边访问，链表的插入删除，HashTable访问 O(logN) 对数级: 二分搜索，二叉树 O(n) 线性级：数组遍历，链表的查找 O(nlogN) 线性对数级：快速排序，归并排序 O(n^2) 平方级：冒泡排序、选择排序、插入排序 O(2^n) 指数级：图、旅行商问题
下一篇：
学编程为什么要学数据结构？