算法笔记（一）

算法复杂性分析

public static int sum(int n){
    int partialSum;
    partialSum=0;              //1
    for(int i=1;i<n;i++){      //2
        partialSum+=i*i*i;     //3
    }
    return partialSum;         //4
}

对于这个程序的算法复杂度分析，声明的变量时间不计。第一行和第四行各占一个时间单元，第三行每执行一次占4个时间单元（两次乘法，一次加法，一次赋值）。执行 N次共占用4N个时间单元。第二行初始化为i=1，所有的这些自增运算为N个单元时间，一共2N+2个时间单元。总量就是6N+4个时间单元。O（6N+4）=O（N）。

• 法则一（for循环）

  for循环是该for循环内的运行次数乘以迭代次数。

• 法则二（嵌套的for循环）

  一组内的嵌套循环乘以组内所有的for循环的大小的乘积

• 法则三（顺序语句）

  其中最大值就是所得的运行时间。

• 法则四（if/else语句）

  比较复杂的一个过程，如果有函数调用，首先要分析函数调用的时间复杂度。如果有递归过程，存在着多数选择。（有些递归会多次重复计算同样的式子，这时候使用动态规划好于使用递归）。

线性表、链表数据结构

简单来说，对表的所有操作都可以使用数组来完成。不过插入和删除的花费却潜藏的巨额的开销。举个例子来说，当在位置0需要插入一条数据的时候，就需要把所有的数据向后移一位空间出来。因此就多出来一种数据结构叫做链表。

• 简单链表

  为了避免删除和插入的线性开销，我们需要保证表可以不连续存储，否则表的每个部分都可能需要全部移动。

  数据结构，这些节点在内存中是不相连的，每个节点均包含有表元素和该元素后继元的节点的链。我们称之为next链。最后一个单元的next链为null。

• 双链表

  指向最后节点的链并不包含最后节点的前驱节点的任何信息。让每个节点指向它在表中的前驱节点的链。

  public static <Type> void print(Collection<Type> coll){
      Iterator <Type> itr =coll.iterator();
      while(itr.hasNext()){
          Type item=itr.next();
          System.out.println(item);
      }
  }
  

  Collection中的remove方法的有点在于，首先必须精确找到这个要被删除的项，知道了准确的位置，删除的开销就会少很多。（例子：在集合中，每隔一个项删一项，使用迭代器的方式会很高效）。

队列、栈结数据结构

栈是限制插入和删除只能在一个位置上进行的表。该位置是表的末端。叫做栈的顶 。对栈的基本操作是pop和push，前者相当于弹出，后者相当于插入。栈叫做LIFO（后进先出的表）

栈的实现

由于栈是一个表，所以使用ArrayList和LinkedList都可以实现栈。大部分情况下他们都是最优的实现选择。

• 链表实现
• 数组实现

应用

• 平衡符号

  public void test(Char[] symbols){
      Stack<Character> stack=new Stack<>();
      for(char sym:symbol){
          if(sym.equals("("))
          stack.push("(");
          else stack.pop();
      }
      if(stack.isEmpty()) return true;
      return false;
  }
  

• 后缀表达式

  后缀记法或者叫逆波兰

• 方法调用

  栈帧（stack frame），当栈溢出的时候，在java中会抛出一个异常。

  不要用递归来打印一张表。

队列
如同栈一样，无论是使用链表的形式还是数组形式，都能实现队列，O（1）的运行时间。