最大子序列和问题 算法与数据结构

最大子序列和问题

问题 给定(可能有负数)整数序列A1, A2, A3..., An, 求这个序列中子序列和的最大值。 思考过程 一、最简单的实现 起点从0开始到数组最后一位元素,终点从起点开始到数组最后一位元素,即遍...
阅读全文
二分查找总结 算法与数据结构

二分查找总结

基本的二分查找:值等于给定值 没有重复值 循环实现: 递归实现: 优点 时间复杂度为O(logn) 空间复杂度O(1) 缺点 只能用于线性表数组,不能用于链表,因为二分法要用到按照数组下标随机访问元素...
阅读全文
图Graph 算法与数据结构

图Graph

图的基本概念 顶点(vertex) 边(edge) 度 入度 出度 有向图 无向图 带权图 储存方式 矩阵 稀疏图 浪费空间 邻接表 节省空间,但查找两个顶点是否相邻比较耗费时间。如果链太长,可以用跳...
阅读全文
哈希表|散列表|hash表 算法与数据结构

哈希表|散列表|hash表

原理 数组可以利用数组下标实现随机访问,时间复杂度为O(1),但数组下标只能是非负整数,对于key不是非负整数的数据,可以利用哈希函数,计算出散列值,作为数组下标,将数据存储在数组中对应下标的位置,即...
阅读全文