数据结构

（笔记）数据结构第一讲-基本概念

陈越 何钦铭

Posted by 王晗 on October 29, 2017

第一讲 基本概念

空间复杂度S（n）

根据算法写成的程序在执行时占用储存单元的长度。

时间复杂度T（n）

根据算法写成的程序在执行时耗费时间的长度。

例题1

	void Print(int N){

    	if(N){

        	Print(N-1);

            printf("%d\n",N);

        }

        return;

    }
物理存储:每递归一次需要申请一个方法临时变量的储存内存
100000 99999 99998 …… 1 ……

|——–|——–|——–|——–|


	PrintN(100000)

      PrintN(99999)

        PrintN(99998)

          PrintN(99997)

            ......

              PrintN(0)

空间复杂度

S（n）=N

二分法


	int BinarySearch1(int a[],int n,int x){

    int left=0,right=n-1;

    int i;

    //循环条件一定要注意

    while(left<=right){

    	//此处的mid的计算一定要放在while循环内部，否则mid无法正确更新;并且此处用移位代替除以2可以提高效率，而且可以防止溢出。

        int i=left+((right-left)>>1);

        if(x>a[i])

            left=i+1;

        else if(x<a[i])

            right=i-1;

        else

            return i;



    }

    //执行流如果走到此处说明没有找到要查找的数字。

    return -1;

    }

注意：

  • right=n-1——>while(left<=right)——>right=i-1

    right=n——>while(left<right)——>right=i

  • 大部分人喜欢在最开始就判断arr[mid]与x相等，但是这样是不明智的，因为相等情况在大多状况下都是少数，写在开始的话，每次循环都需要判断一次相等，浪费时间，效率太低。

复杂度渐进表示法

$T(n)=O(f(n))表示存在常数C>0,n_0>0使得当n>=n_0时有T(n)<=C·f(n)$ (上界)

$T(n)=\Omega(g(n))表示存在常数C>0,n_0>0使得当n>=n_0时有T(n)>=C·g(n)$ (下界)

$T(n)=\Theta(h(n))表示同时有T(n)=O(h(n))和T(n)=\Omega(h(n))$ (既是上界也是下界)

不同函数复杂度

复杂度分析小窍门

  • 若两段算法分别有复杂度$T_1(n)=O(f_1(n))和T_2(n)=O(f_2(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))$

  • 若$T(n)是关于n的k阶多项式，那么T(n)=\Theta(n^k)$

  • 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度

  • if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大？？？

应用实例：最大子列问题

例题：$给定N个整数序列{A_1,A_2,…,A_N},求函数f(i,j)=max{0,\sum_{k=1}^{j}{A_k}}的最大值$

算法1


int MaxSubseqSum1(int A[],int N){

  int ThisSum,MaxSum=0;

  int i,j,k;

  for(i=0;i<N;i++){            //i是之列的左端位置

    for(j=i;j<N;j++){          //j是子列右端位置

      ThisSum=0;  //ThisSum是从A[i]到A[j]的子列和

      for(k=i;k<=j;k++)

        ThisSum+=A[k];

      if(ThisSum>MaxSum)       //如果刚得到的这个子列和更大

        MaxSum=ThisSum;        //则更新结果



    }    //j循环结束

  }     //i循环结束

  return MaxSum;

}

时间复杂度：$T(N)=O(N^3)$

算法2


int MaxSubseqSum2(int A[],int N){

  int ThisSum,MaxSum=0;

  int i,j;

  for(i=0;i<N;i++){            //i是之列的左端位置

    ThisSum=0;  //ThisSum是从A[i]到A[j]的子列和

    for(j=i;j<N;j++){          //j是子列右端位置

      //对于相同的i,不同的j,只要在j-1次循环的基础上累加一项即可

      ThisSum+=A[j];

      if(ThisSum>MaxSum)       //如果刚得到的这个子列和更大

        MaxSum=ThisSum;        //则更新结果



    }    //j循环结束

  }     //i循环结束

  return MaxSum;

}

时间复杂度：$T(N)=O(N^2)$

算法3：分而治之


int Max3( int A, int B, int C )            // 返回3个整数中的最大值

{

    return A > B ? A > C ? A : C : B > C ? B : C;

}

 //分治法求List[left]到List[right]的最大子列和

int DivideAndConquer( int List[], int left, int right )

{

    int MaxLeftSum, MaxRightSum;     //存放左右子问题的解

    int MaxLeftBorderSum, MaxRightBorderSum;    //存放跨分界线的结果



    int LeftBorderSum, RightBorderSum;

    int center, i;



    if( left == right )  //递归的终止条件，子列只有1个数字

        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++ ) {   

        RightBorderSum += List[i];  

        if( RightBorderSum > MaxRightBorderSum )  

            MaxRightBorderSum = RightBorderSum;  

    } //右边扫描结束

   

    //下面返回"治"的结果 

    return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );  

}  

   

int MaxSubseqSum3( int List[], int N )  //保持与前2种算法相同的函数接口 

{ 

    return DivideAndConquer( List, 0, N-1 );  

}

时间复杂度：$T(N)=2T(N/2)+cN, T(1)=O(1)$

         $=2[2T(N/2^2)+cN/2]+cN$

         $=2^kO(1)+ckN       其中N/2^k$

         $=NO(1)+clog_2N\times N$

         $=O(NlogN) $

####算法4：在线处理


int MaxSubseqSum1(int A[],int N){

  int ThisSum,MaxSum;

  int i,j;

  ThisSum=MaxSum=0;

  for(i=0;i<N;i++){

      ThisSum+=A[j];           //向右累加

      if(ThisSum>MaxSum)       //如果刚得到的这个子列和更大

        MaxSum=ThisSum;        //则更新结果

      else if(ThisSum<0)       //如果当前子列和为负

        ThisSum=0;             //则不可能使后面的部分和增大，抛弃之

  }

  return MaxSum;

}

时间复杂度：$T(N)=O(N)$

“在线”的意思是指每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解。

####习题：01-复杂度2 Maximum Subsequence Sum（25 分）

Given a sequence of K integers ${N_1,N_2,…,N_K}$. A continuous subsequence is defined to be ${N_i,N_{i+1},…,N_j}$ where $1≤i≤j≤K$. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer $K (≤10000)$. The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

10

-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:

10 1 4

正确答案：


#include <vector>

#include <iostream>

 

using namespace std;

 

int main()

{

    int n;

    cin>>n;

    vector<int> v(n,0); 

    for(int i=0;i<n;++i)

        cin>>v[i];

         

    bool allng=true;

    bool has0=false;

    bool notp=true;

 

    for(int i=0;i<n;++i)

    {

        if (v[i]>=0)

            allng=false;

        if(v[i]==0)

            has0=true;

        if(v[i]>0)

            notp=false;

    }

    if(allng)

    {

        cout<<0<<" "<<v[0]<<" "<<v[n-1];

        return 0;

    }

    if(has0&&notp)

    {

        cout<<0<<" "<<0<<" "<<0;

        return 0; 

    }

     

    int sum,thissum,start,end;

    sum=thissum=start=end=0;

    int pos1=0;

     

    for(int i=0;i<n;++i)

    {

        thissum+=v[i];

        if(thissum>sum)

            {

                sum=thissum;

                start=pos1;

                end=i;

            }

        else if (thissum<0)

        {

            thissum=0;

            pos1=i+1;

        }

         

    }

     

    cout<<sum<<" "<<v[start]<<" "<<v[end];

    return 0;

}

我的答案：（负数和为0测试未通过）


#include <stdio.h>

int MaxSubseqSum(int A[],int N,int*,int*);



int main() {

    int N;

    scanf("%d",&N);

    int A[N];

    for(int i=0;i<N;i++){

        scanf("%d",&A[i]);

    }

    int MaxSum=0;

    int left=0,right=0;

    MaxSum=MaxSubseqSum(A,N,&left,&right);

    printf("%d %d %d",MaxSum,left,right);

    return 0;

}



int MaxSubseqSum(int A[],int N,int *left,int *right){

    int ThisSum,MaxSum,StartPosition;

    int i;

    ThisSum=MaxSum=StartPosition=0;

    for (int i = 0; i <N; ++i) {

        ThisSum+=A[i];

        if (ThisSum>MaxSum){

            MaxSum=ThisSum;

            *left=A[StartPosition];

            *right=A[i];

        }



        else if(ThisSum<0){

            ThisSum=0;

            StartPosition=i+1;

        }



    }

    if(*left==0&&*right==*left&&StartPosition>0){

        *left=A[0];

        *right=A[StartPosition-1];

    }



    return MaxSum;

}
  • 知识点：c语言不能传递引用，c++可以
FEATURED TAGS
数据结构
FRIENDS