算法的概念
算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务，一般，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。
算法重要的是其的思想，而不是其所实现的某种语言，它是独立存在的一种解决问题的方法和思想。
算法的特性
输入：算法具有0个或多个输入
输出：算法至少有1个或多个输出
有穷性：算法在有限的步骤之后会自动结束，而不会无限循环，并且每一个步骤可以在可接受的时间内完成
确定性：算法中的每一步都有确定的含义，不会出现二义性
可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成
算法的效率
执行时间反应算法效率，实现算法程序的执行时间可以反应出算法的效率，也就是算法的优劣
但是单纯的依靠运行时间来比较算法的优劣并不一定是客观准确的，程序的运行，还依靠了运行环境等客观条件，所以并不能单纯的从运行时间来分别算法的好坏。
时间复杂度
假定计算机执行算法每一个基本操作的时间是一个固定的时间单位，那么有多少个基本操作就代表会花费多少时间单位，即使对于不同的程序运行环境来说，确切的程序运行时间是不同的，但是对于算法运行所花费的时间单位的数量级是相同的，所以可以忽略机器环境的影响而客观的反应算法的时间效率。我们采用“大O记法来表示”

大O记法


“大O记法”：对于单调的整数函数f，如果存在一个整数函数g和实常数c>0，使得对于充分大的n总有f(n)<=c*g(n)，就说函数g是f的一个渐近函数（忽略常数），记为f(n)=O(g(n))。也就是说，在趋向无穷的极限意义下，函数f的增长速度受到函数g的约束，亦即函数f与函数g的特征相似。
时间复杂度：假设存在函数g，使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n))，则称O(g(n))为算法A的渐近时间复杂度，简称时间复杂度，记为T(n).
算法完成工作最少需要多少时间单位，就是最优时间复杂度
算法完成工作最多需要所少时间单位，就是最坏时间复杂度
算法完成工作平均需要多少基本操作，就是平均时间复杂度

时间复杂度的基本计算规则
基本操作，即只有常数项，认为其时间复杂度为O(1)
顺序结构，时间复杂度按加法进行计算
循环结构，时间复杂度按乘法进行计算
分支结构，时间复杂度取最大值
判断一个算法的效率时，往往只要关注操作数量的最高次项，其它次要项和常数项可以忽略
在没有特殊说明时，我们往往分析的算法时间复杂度是指最坏时间复杂度
常见时间复杂度


常见时间复杂度之间的关系
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
数据结构
为了解决问题，将数据保存下来，然后根据数据的存储方式来设计算法实现进行处理，那么数据的存储方式不同就会导致需要不同的算法进行处理，我们希望算法解决问题的效率越快越好，所以就需要思考如何保存数据，这就是数据结构。换句话说，数据结构指数据对象中数据元素之间的关系。高效的程序需要在数据结构的基础上设计和选择算法。也可以说程序是数据结构和算法之和。
抽象数据类型（Abstract Data Type）
ADT的含义是指一个数据模型以及定义在此模型上的一组操作。即把数据类型和数据类型上的运算联合在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上的运算实现与这些数据类型和运算在程序中的引用隔开，使其相互独立。
最常用的数据运算类型有：插入、删除、修改、查找、排序

 Caché 算法与数据结构
第一章 Caché 算法与数据结构 基础和概念 ☆☆☆☆☆
第二章 Caché 算法与数据结构 数组原理 ☆☆☆☆☆
第三章 Caché 算法与数据结构 链表原理 ☆☆☆☆☆
第四章 Caché 算法与数据结构 栈原理 ☆☆☆☆☆ 
第五章 Caché 算法与数据结构 队列原理 ☆☆☆☆☆
第六章 Caché 算法与数据结构 循环队列 ☆☆☆
第七章 Caché 算法与数据结构 双端队列 ☆☆☆
第八章 Caché 算法与数据结构 散列表 ☆☆☆☆☆
第九章 Caché 算法与数据结构 二叉树 ☆☆☆
第十章 Caché 算法与数据结构 二叉堆 ☆☆☆ 
第十一章 Caché 算法与数据结构 优先队列 ☆☆☆
第十二章 Caché 算法与数据结构 冒泡排序 ☆☆☆☆☆
第十三章 Caché 算法与数据结构 鸡尾酒排序 ☆☆☆
第十四章 Caché 算法与数据结构 快速排序 ☆☆☆
第十五章 Caché 算法与数据结构 堆排序 ☆☆☆
第十六章 Caché 算法与数据结构 计数排序 ☆☆☆
第十七章 Caché 算法与数据结构 希尔排序 ☆☆☆
第十八章 Caché 算法与数据结构 选择排序 ☆☆☆
第十九章 Caché 算法与数据结构 插入排序 ☆☆☆
第二十章 Caché 算法与数据结构 归并排序 ☆☆☆
第二十一章 Caché 算法与数据结构 基数排序 ☆☆☆
第二十二章 Caché 算法与数据结构 桶排序 ☆☆☆
第二十三章 Caché 算法与数据结构 二分查找 ☆☆☆☆
第二十四章 Caché 算法与数据结构 斐波那契查找 ☆☆☆☆
第二十五章 Caché 算法与数据结构 插值查找 ☆☆☆☆
 前言


经过一个月的连载《Caché 算法与数据结构》基础系列终于连载完毕。主要讲解了数据结构，排序算法，查找算法。此次《Caché 算法与数据结构》基于应用最普遍的JAVA开发语言，实现了与JAVA数组，堆，栈，MAP，队列，链表等数据结构，方便Caché 实现一些复杂的逻辑结构。由于个人能力有限，还有一些比较高级的算法与数据结构还没有实现，例如AVL树，2-3树，2-3-4树，B树，Tire树，贪心算法，分治算法，动态规划，回溯枚举算法，堵塞队列，并发队列，斐波那契堆等。对于有一些问 题的分析难免会有纰漏。实例中的解决方法也不是尽善尽美，每一章节笔者都留有思考 ，感兴趣的朋友可以思考实现完成之后留言一起讨论。也希望发现其他问题的朋友 及时向笔者反馈。


由于笔者整理的是基础版本，所以不会太难，大家可以对着代码练习一遍，相信会对个人的编程能力和程序员基本思想都有帮助。


 预告

下一期系列将用一个月的时间连载，《Caché 命令大全》，Caché 命令是大家最常用，日常接触最多的。但是相信大部分人针对命令只知道其一，不知道其二，每个命令都一些独特且非常好用的用法，根据28原则，这次《Caché 命令大全》将对所有命令做出一个详细的概述和讲解，每章开始都会有一个我梳理的重点概念。

交流群

QQ群号：410039091
笔者QQ：454115408
公众号：技术理科直男

算法与数据结构之一
1.如何有效的学好算法和数据结构
2.如何计算时间复杂度
3.如何使用LeetCode和剑指office
4.数组和链表
5.堆栈、队列(Stack、Queue)
6.优先队列
7.哈希表：映射(Map) & 集合(Set)
8.树、二叉树、二叉搜索树;


算法和数据结构是程序员的内力;

1.如何有效的学好算法和数据结构

《异类一不一样的成功启示录》作者：马尔科姆


精通一个领域：

Chunk it up(切碎知识点)

Deliberate practicing(刻意的练习)—>不舒服、枯燥、乏味的地方;

Feedback(反馈)---->看高手代码(Github,Leetcode等)


数据结构中的联系

	

切题四件套：

Clarification:

Possible solutions:compare(time/space) 、optimal(加强)等

Coding：(多写)

Test cases

2.如何计算时间复杂度
数据结构与算法的分解：



常用的时间复杂度;




递归思想：一个分叉的树有大量的重复计算;O(2^n)

动态规划思想：时间复杂度为O(n);


Master  Theorem:



3.如何使用LeetCode和剑指office

做题
时间复杂度和空间复杂度
Editor:Atom、Visual Code 、VIm等

FeedBack

Discuss、solutioon;

4.数组和链表
1.数组：可以索引O(1)、插入或删除平均O(n);

2.链表(Linked List):使用于插入和删除很多O(1)，查找O(n);

面试习题：

- 202 Reverse Linked List：反转单链表

主要考代码的实现能力;


detect cycle: 判断链表是否有环(快慢指针);

5.堆栈、队列(Stack、Queue)
图片来源

20.括号匹配是否合法
232、使用堆栈实现队列：堆栈1永远只进，堆栈2用于只出，并堆栈2不为空，将其导入堆栈1中;
225、使用队列实现堆栈;

6.优先队列
正常入、按照优先级出;

实现方式：

1.堆(最小堆、最大堆)来实现，

2.树来实现

Heap wiki:


703.实时判断数据流中前k大的元素—>堆实现、优先队列
239.滑动窗口最大值---->使用优先队列时间复杂度降级，不用排序了;维护堆是O(logk), 查看是O(1),总体是O(NlogK);  也可以使用deque双端队列;


队列中的元素中最大值始终放在最左端，其中元素数量不一定为k;O(n);

7.哈希表：映射(Map) & 集合(Set)
哈希函数：计算出存放的正确存储位置，这样查找时时间复杂度为O(1)

哈希的冲突：拉链法解决,即每一个后面存放多个(链表的形式);

集合不允许存放重复元素

HashMap(哈希表实现O(1)，无序)) vs TreeMap(二叉树实现O(logn)，有序)

HashSet vs TreeSet


242、有效的字母异位词：第一种方法对每个字符串排序(Nlog(N)); 第二种使用map来计数;O(n)
1.两数和:
15.三数和为0，暴力三层循环O(n3)，集合O(n2)空间复杂O(N);  先排序，在两头查找法O(N2)

8.树、二叉树、二叉搜索树;

本篇是算法与数据结构系列的目录：

1.排序算法总结

2.红黑树

3.在线生成红黑树
作者：yiyele

转载请保留原文地址：http://write.blog.csdn.net/mdeditor#!postId=74317447
如果本文对您有所帮助，欢迎您扫码下图所示的微信支付点赞码对本文进行打赏。