一、前言
 
都说数据结构与算法分析是程序员的内功，想要理解计算机世界就不能不懂点数据结构与算法，然而这也备受争议，因为大多数的业务需求都用不上数据结构与算法，又或者说已经有封装好的库可以直接调用，例如Java中的ArrayList与LinkedList，直接调用add、remove等方法就已经可以完成插入删除等基本操作，实现业务逻辑，而无需关注其内部实现。如果说一样东西有没有用是根据用不用得上来衡量的话，那么只写业务逻辑确实没什么卵用，但是个人觉得有没有用是根据对自己有没有帮助来判断的，对自己有帮助==这个东西对我有用。
 
实话说，自己一开始是因为要准备企业面试才打算学习的数据结构与算法（趁着当当网搞活动的时候买了本《数据结构与算法分析Java语言描述》，打算在寒假的时候看），期间也看过不少文章，开复先生就曾经写过一篇文章聊算法的重要性，当时就觉得懂算法的人好厉害。但真正让我开始重视数据结构与算法的是Leetcode的第一道题目TwoSum.
 
给定一个数组和一个得数，返回数组中两个数字相加等于得数的这两个数字的索引 
 example
 
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
 
我的解法
 
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int result[] = new int[2];
        for(int x = 0;x<nums.length;x++){
            for(int y = x+1;y<nums.length;y++){
                if((nums[x]+nums[y])==target){
                    result[0] = x;
                    result[1] = y;
                }
            }
        }
        return result;
    }
}
 
别人的解法
 
public int[] twoSum(int[] numbers, int target) { 
    int[] result = new int[2]; 
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
    for (int i = 0; i < numbers.length; i++) { 
        if (map.containsKey(target - numbers[i])) { 
            result[1] = i + 1; 
            result[0] = map.get(target - numbers[i]); 
            return result; 
        } 
        map.put(numbers[i], i + 1); 
    } return result; 
}
 
虽然都可以运行，但是明显别人的解法比我的优雅的太多太多。我的想法是用两个循环穷举，而别人是用了HashMap来存储数据，并且在循环中同时进行插入和判断，时间复杂度我的是O(n2)，而别人的是O(n)，如果数据规模大，运行时间则相差巨大。 
 可见同样的问题，不同人采取的解决方式是可以体现出差别的，这就关系到数据结构与算法
 
 
 
目前对数据结构与算法的理解 
 数据结构：为了解决问题采用的更有效率的数据组织方式 
 算法：为了解决问题采用的更加快速的程序设计思想
 
 
作为一个想在技术领域打拼十年的菜鸟，有必要学习数据结构与算法。讲真，这还是挺难学的，《数据结构与算法Java语言描述》这本书看了有一半，后面的还看不太懂，前面的又忘了，觉得有必要总结一下。 
 网络上也有人非常详细的总结了这本书前两章的内容数据结构与算法分析（一）：基础算法分析，在这里就不重复造轮子了，只总结一些想加深印象的内容。
 
二、如何进行算法分析
 
（一）分析前提
 
计算模型：假设有无限内存的模型机做任一件简单的工作都恰好花费一个时间单位，并且不存在矩阵求逆或排序之类的想象操作。
 
（二）分析重点
 
1.运行时间（时间复杂度） 
 影响因素：输入大小n以及所使用的算法 
 2.占用内存（空间复杂度） 
 影响因素：算法本身存储占用、输入输出数据占用以及算法运行过程临时占用
 
（三）时间复杂度计算——大O标记法（运行时间的上界，注意简化常数项与低阶项）
 
example:计算$\sum_{i=0}^N i^3$的运行时间
 
public static int sum(int n) {
      int partialSum;
       partialSum = 0;
       for(int i = 1; i <= n; i ++)
       partialSum += i * i * i;
       return partialSum;
}
 
 
 
所有的声明均不计时间 
 第3行和第6行各占一个时间单元 
 第5行每执行一次占用4个时间单元（两次乘法、一次加法、一次赋值），执行N次共4N个时间单元 
 第4行初始化i占用1个时间单元、测试i<=n为N+1个时间单元、i++自增运算为N个时间单元，共2N+2个时间单元 
 忽略调用方法和返回值的开销，共6N+4个时间单元 
 故该方法是O(N)的
 
 
快速判断法则： 
 1.for循环 
 一个for循环的运行时间至多是该for循环内部那些语句（包括测试）的总运行时间乘以迭代的次数 
 2.嵌套的for循环 
 从里向外，一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有的for循环的大小的乘积 
 3.顺序语句 
 各语句运行时间求和 
 4.if/else语句 
 一个if/else语的运行时间不超过 判断的运行时间+if语句/else语句中较长的运行时间
 
分析的基本策略是从内部（或最深层的部分）向外展开工作的。有方法调用则首先分析方法调用；有递归过程，则具体情况具体分析
 
（四）空间复杂度计算
 
当算法占用空间大小不随数据量n变化而变化，其空间复杂度可记为O(1) 
 当算法占用空间大小随数据量n变化而线性变化，其空间复杂度可记为O(n)
 
 
 
在程序开发中，我们所指的复杂度不做特别说明的情况下，就是指时间复杂度。现在的硬件发展速度之快使得我们完全可以不用考虑算法所占的内存，通常都是用空间换取时间。加之算法的空间复杂度比较难算，所以我们都侧重于时间复杂度。
 
 
三、数据结构与算法分析学习目标
 
学习，要以解决问题为导向，因此要： 
 1.了解各种数据结构的结构性质，以便遇到问题可以快速选取合适的数据结构 
 2.了解各大算法的性能及应用场景，以便遇到问题可以快速选取合适的算法
 
 
参考资料及资源站点 
 《数据结构与算法分析：Java语言描述》 
 数据结构与算法动态可视化中文站点 
 数据结构与算法/leetcode/lintcode题解

数据结构与算法分析经典高清珍藏版 
 
 
http://download.csdn.net/detail/oyy_ou/5071561
 

 

数据结构与算法分析（一）
 


 
文章目录
 
数据结构与算法分析（一）
第一章 基本概念
第一节 数据结构
1.1 基本术语和概念
1.2. 数据的逻辑结构
1.3 数据的存储结构
1.4 抽象数据类型
    
第二节 算法及性能分析
2.1 算法
2.2时间复杂度
2.2.1计算方法：
2.2.2 一般法则
     
2.3 空间复杂度
2.4 递归：
1.它是否就是循环逻辑？
2.实现递归的基本准则：
    
   
  
 

 
 
 
数据结构 + 算法 = 程序
 数据结构主要研究组织大量数据的方法，算法分析是对算法运行的时间的评估。
 
 
第一章 基本概念
 
第一节 数据结构
 
1.1 基本术语和概念
 
 
（1）数据（Data）：是指描述客观事物的符号，是计算机可以操作的对象，能被计算机识别，并输入给计算机处理的符号或符号集合。万物皆可为数据，不止局限于数字，字符，一个图像，一段视频都是数据。
 
（2）数据对象（data object）：是性质相同数据元素的集合，是数据的一个子集。例如所有的视频数据可以成为一个数据对象。
 
（3）数据元素（data element）：是数据的基本单位。也叫结点或记录。例如一个视频。
 
（4）数据项（data item）：是数据的最小单位。例如视频里的每一帧。
 
（5）数据结构（data structure）：是数据元素之间的组织方式。
 
1.2. 数据的逻辑结构
 
​ 逻辑结构（logical structure）：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。
 
数据结构有四种不同的逻辑结构：
 
（1）集合结构：集合中的各个元素是平等的，元素之间没有任何联系，仅是共处于同一集合。
 
 
（2）线性结构：元素结构关系是一对一的，并且是一种先后的次序。
 
 
（3）树形结构：元素结构关系是一对多的，并且存在父子级。
 
 
（4）图形结构：元素结构关系是多对多的。
 
 
1.3 数据的存储结构
 
​ 存储结构（storage structure） 也成为物理结构（physical structure），是指数据的逻辑结构在计算机中的存储形式，一般可以反映数据元素之间的逻辑关系。
 
数据结构有两种不同的存储结构：
 
（1）顺序存储结构：把数据元素存储在地址连续的存储单元中，数据间的逻辑关系和物理关系是一致的。
 
 
（2）链式存储结构：把数据元素存储在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。
 
 
1.4 抽象数据类型
 
抽象数据类型（abstract data type，ADT） 是一些操作的集合。描述数据类型的方法不依赖于具体实现，与存放的机器无关，与数据存储的物理结构无关，与实现操作的算法和编程语言无关，只描述数据对象集合相关操作集“是什么”，并不干涉“如何做到”。
 
 
 
表ADT 栈ADT 队列ADT
 
 
第二节 算法及性能分析
 
2.1 算法
 
算法（algorithm） 是一系列为特定问题而规定指令的集合。有以下特性：
 
 
输入，是指算法具有零个或多个输入。
 
 
输出，是指算法至少有一个或多个输出。
 
 
有穷性，是指算法在执行有限的步骤之后，自动结束而不是出现无限循环，并且每一个步骤在可接受的时间内完成。
 
 
确定性，是指相同输入只能有一个唯一的输出结果，不会出现二义性。
 
 
可行性，是指算法每一步骤都必须可行，能够通过有限的执行次数完成。
 
 
2.2时间复杂度
 
​ 算法的时间复杂度，也就是算法的时间量度，记作： T(n)=O(f(n))。它表示随问题规模 n的增大算法执行时间的增长率和 f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中 f(n)是问题规模 n的某个函数。
 
2.2.1计算方法：
 
1.用常数1取代函数中所有的常数
 
2.只保留最高项
 
3.最好情况时间复杂度：代码在最坏情况下执行的时间复杂度。
 
 
 
常用的时间复杂度所耗费的时间从小到大依次是
 
 
O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(n!) < O(nn)
 
 
2.2.2 一般法则
 
法则 1-----for循环
 
一次for循环的运行时间至多是该for循环内语句的运行时间X循环的次数。
 
for(i = 1 ; i <= n ; i++)
{
    x = x + 1;		/* 时间复杂度为O(n) */
}
 
法则 2-----嵌套的for循环
 
从里向外分析，在一组嵌套循环内部的一跳语句总的运行时间为该语句的运行时间X该组所有for循环的大小的乘积。
 
for( i = 0; i < n; i++)
{
    for(j = 0; j < n; j++)
        k++;		/* 时间复杂度为O(n*n) */
}
 
法则 3-----顺序语句
 
将各个语句的运行时间求和即可，其中的最大值即为运行时间。
 
for(i = 1 ; i <= n ; i++)
{
    x = x + 1;		/* 时间复杂度为O(n) */
}
for( i = 0; i < n; i++)
{
    for(j = 0; j < n; j++)
        k++;		/* 时间复杂度为O(n*n) */
}
/* 总时间复杂度为O(n*n) */
 
法则 4-----while语句
 
int count = 1;
while(count < n){
	count *= 2;
	/*时间复杂度为 O(1) 的程序步骤序列*/
}

/* 2^x = n  时间复杂度为O(log n) */
 
2.3 空间复杂度
 
算法的空间复杂度是通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作： S(n)=O(f(n))S(n)=O(f(n)) S(n) = O(f(n))S(n)=O(f(n)) 。其中，n 为问题的规模， f(n)f(n) f(n)f(n) 为语句关于 n 所占存储空间的函数。
 
2.4 递归：
 
int F(int x)
{
    if(x == 0)
        retuen 0;
    else 
        return 2 * F(x-1) + X * X;
}
 
1.它是否就是循环逻辑？
 
答案是：虽然函数会用到这个函数本身，但是我们并没有用函数本身来定义函数的一个特定的实例。即使用F（5）来得到F（5）的值才是循环，通过F（4）来得到F（5）的值不是循环的。
 
2.实现递归的基本准则：
 
基准情形：递归中必须要有某些基准情形，他们不用递归就能求解。
 
不断推进：对于那些需要递归求解的情形，递归调用必须总能朝着产生基准情形的方向推进。
 
设计法则：假设所有的递归调用都能运行。
 
合成效益法则：在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。

这段时间，该开始数据结构与算法分析的学习了。跟以前一样，学习同时整理成博文是个不错的学习方式，因此，后面一段时间将对数据结构与算法分析进行讲解学习，希望有兴趣的同学一起讨论学习。
 
 
数据结构，即组织大量数据的方法；算法分析，即算法运行时间的估计。很多时候，写出一个工作程序并不够，如果这个程序需要在巨大的数据集上运行，那么运行时间就成为了重要的问题。
 
1 级数
 
（1）$\sum\limits_{i = 1}^\infty  {\frac{i}{{{2^i}}} = 2}$ 
 （2）$\sum\limits_{i = 1}^N {{i^k}}  \approx \frac{{{N^{k + 1}}}}{{\left| {k + 1} \right|}},k \ne  - 1$ 
 （3）调和数 ${H_N} = \sum\limits_{i = 1}^N {\frac{1}{i}}  \approx {\log _e}N$
 
2 证明数据结构分析中的结论的常用方法
 
（1）归纳法证明 
 （2）证法证明
 
3 递归的基本法则
 
当一个函数用它自己来定义时就称为递归。 
 （1）基准情形 
 必须总要有某些基准情形，它无需递归就能解出 
 （2）不断推进 
 对于那些需要递归求解的情形，每一次递归调用都必须要使状况朝向一种基准情形推进 
 （3）设计法则 
 当设计递归程序时一般没有必要知道簿记管理的细节，不必试图追踪大量的递归调用 
 （4）合法效益法则 
 在求解一个问题的同一个实例时，切勿在不同的递归调用中做重复性的工作，如使用递归计算斐波那契数之类简单数学函数的值就不高效