复杂度的渐进表示法

• $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;
      }
  }

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