复杂度的渐进表示法

• T(n)=O(f(n))表示存在常数C>0,n_0>0使得当n>n_0时有T(n)<C\cdot f(n),即上界
• T(n)=\Omega (g(n))表示存在常数C>0,n_0>0使得当n>n_0时有T(n)>C\cdot g(n)，即下界
• T(n)=\Theta(h(n))表示同时有T(n)=O(f(n)) 和 T(n)=\Omega(h(n))
• 性质：上下界不唯一
• log(n)<n<nlog(n)<n^i<2^n<n!
• T_1(n)+T_2(n)=max(O(f_1(n),O(f_2(n))))
• T_1(n)\times T_2(n)=O(f_1(n)\times f_2(n))

最大子列和问题

1. 暴力循环遍历所有子列，时间复杂度O(n^3)

   int MaxSubSeqsum(int A[],int N){
       int i,j,k;
       int ThisSum,MaxSum=0;
       for(i=0;i<N;i++){
        for(j=i;j<N;j++){
            ThisSum=0;
               for(k=i;k<=j;k++){
                   ThisSum+=A[k];
               }
               if (ThisSum>MaxSum) MaxSum=ThisSum;
           }
       }
       return MaxSum;
   }

2. 避免部分重复计算，时间复杂度可降为O(n^2）

   int MaxSubSeqsum(int A[],int N){
    int i,j;
    int ThisSum,MaxSum=0;
    for(i=0;i<N;i++){
        ThisSum=0;
        for(j=i;j<N;j++){
            ThisSum+=A[j];
            if(ThisSum>MaxSum) MaxSum=ThisSum;
        }
    }
    return MaxSum;
   }

3. 分而治之，时间复杂度分析： T(1)=O(1) \begin{equation} \begin{aligned} T(N) &=2 T(N / 2)+O(N) \\\ &=2[2 T((N / 2) / 2)+O(N / 2)]+O(N)\\\ &=2^{2} T\left(N / 2^{2}\right)+2 \cdot O(N) \\\ &=\cdots=2^{k} T\left(N / 2^{k}\right)+k \cdot O(N) \end{aligned} \end{equation}

 int Max3(int a,int b,int c){
     return a>b?a>c?:a:c:b>c?b:c;
 }  
int DivideAndConquer(int List(),int left,int right){
    int MaxLeftSum,MaxRightSum;
    int MaxLeftBorderSum,MaxRightBorderSum;
    int LeftBorderSum,RightBorderSum;
    int center,i;
    if(left==right){
        if(List[left]>0) return List[left];
        else return 0;
    }

    center=(left+right)/2;
    MaxLeftSum=DivideAndConquer(List,left,center);
    MaxRightSum=DivideAndConquer(List,center+1,right);

    MaxLeftBorderSum=0;LeftBorderSum=0;
    for(i==center;i>=left;i--){
        LeftBorderSum+=List[i];
        if(LeftBorderSum>MaxLeftBorderSum)
            MaxLeftBorderSum=LeftBorderSum;
    }

    MaxRightBorderSum=0;RightBorderSum=0;
    for(i==center+1;i<=right;i++){
        LeftBorderSum+=List[i];
        if(RightBorderSum>MaxRightBorderSum)
            MaxRightBorderSum=RightBorderSum;
    }
    return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);
}
int MaxSubSeqSum(int List[],int N){
    return DivideAndConquer(List,0,N-1);
}

4. 在线处理，时间复杂度O(n)

   int MaxSubSeqsum(int A[],int N){
       int i;
       int ThisSum,MaxSum=0;
       for(int i=0;i<N;i++){
           ThisSum+=A[i];
           if (ThisSum>MaxSum) MaxSum=ThisSum;
           else if(ThisSum<0) ThisSum=0;
       }
       return MaxSum;
   }

线性表

• 定义：同类元素构成的有序序列的线性结构
• 根据存储方式的不同可分为 1.顺序存储（数组）：物理上相邻 2.链式存储（链表）：逻辑上相邻
• 广义表：表中表

堆栈

• 后入先出，LIFO(Last In First Out)

• 栈的顺序存储实现：由一个一维数组和一个记录栈顶元素位置的变量组成

#define MaxSize 1e9
typedef struct SNode *Stack;
struct SNode{
    ElementType Data[Maxsize];
    int top;
};
void initStack(Stack ptrS){
    top=-1;
}
void push(Stack ptrS,ElementType item){
    if(ptrS->top==MaxSiz-1) {
        printf("堆栈满");return;
    }else{
        ptrS->Data[++(ptrS->top)]=item;
        return;
    }
}
ElementType pop(Stack ptrS){
    if(ptrS->top==-1){
        printf("stack is empty");
        return ERROR;
    }else{
        return ptrS->Data[(ptr->top)--];
    }
}

• 堆栈的链式存储

  typedef struct SNode *Stack;
  struct SNode{
      ElementType Data;
      struct SNode *Next;
  };

  Stack CreateStack(){
      Stack S;
      S=(Stack)malloc(sizeof(struct SNode));
      S->Next=NULL;
      return S;
  }

  int IsEmpty(Stack s){
      return s->Next==NULL;
  }

  void Push(ElementType item,Stack S){
      struct SNode *tempCell;
      tempCell=(Stack)malloc(sizeof(struct SNode));
      tempCell->Data=item;
      tempCell->Next=S->Next;
      S->Next=tempCell;
  }

  ElementType Pop(Stack S){
      struct SNode *firstCell;
      ElementType topItem;
      if(IsEmpty(S)){
          printf("stack is empty"); return ERROR;
      }else{
          FirstCell=S->next;
          S->Next=firstCell->Next;
          topItem=firstCell->Data;
          free(firstCell);
          return topItem;
      }
  }

• 一个数组实现两个堆栈，可通过两个数组方向生长的方式。