數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)課程中基礎(chǔ)中的基礎(chǔ)，將其學(xué)透徹百利而無(wú)一害，可惜自己當(dāng)年學(xué)的時(shí)候沒(méi)好好聽(tīng)，好在現(xiàn)在還不算晚。為了勉勵(lì)自己以及復(fù)習(xí)，我將在此更新自己所學(xué)的筆記，所用教材為網(wǎng)易云課堂陳越、何欽銘老師所授課的《數(shù)據(jù)結(jié)構(gòu)》課程。那么，就開(kāi)始吧！

1.1 什么是數(shù)據(jù)結(jié)構(gòu)

例1：書(shū)架擺書(shū)。

小結(jié)：解決問(wèn)題方法的效率和數(shù)據(jù)的組織方式有關(guān)

例2：寫程序?qū)崿F(xiàn)一個(gè)函數(shù)PrintN,使傳入正整數(shù)N的參數(shù)后，能順序打印從1到N的全部正整數(shù)

結(jié)果：輸入100000，循環(huán)算法跑了一會(huì)，遞歸算法直接掛掉
原因：計(jì)算機(jī)一般不愿意跑遞歸，因?yàn)閷?duì)空間占用很恐怖，一旦空間不夠便會(huì)爆掉。

小結(jié)：解決問(wèn)題方法的效率和空間利用效率有關(guān)

例3：

image.png

辣雞寫法：

image.png

標(biāo)準(zhǔn)寫法：

image.png

Clock()函數(shù)

image.png

若時(shí)間太短，就重復(fù)多次
自己寫的例子：

  #include"stdio.h"
  #include"math.h"
  #include"time.h"

  clock_t start,stop;
  double duration;

  double f1(double x)
  {
    double p=0,i;
    for(i=1;i<100;i++)
    {
        p+=pow(x,i)/i;
    }
    return p+1;
  }
  
  int main()
  {
    double A1;
    double x=1.1;
    double i=100;
    start=clock();
    for(int j=1;j<10000;j++)
    {
        A1=f1(x);
    }
    stop=clock();
    duration=((double)(stop-start)/CLK_TCK/10000);
    printf("A1=%lf\n",A1);
    printf("%lf\n",duration);
    return 0;
  }

小結(jié)：解決問(wèn)題方法的效率，和算法的巧妙程度有關(guān)

1.2 什么是算法

image.png

簡(jiǎn)單地說(shuō)，f(n)是上界，g(n)為下界，第三種代表上界下界相同.

image.png

實(shí)戰(zhàn)：

image.png

算法1：

image.png

算法2：

image.png

Ps:優(yōu)秀的程序員發(fā)現(xiàn)時(shí)間復(fù)雜度為O（N^2）時(shí)會(huì)想著轉(zhuǎn)換為O（NlogN）

算法3：

image.png

算法4：

image.png

自己寫的代碼：
#include"stdio.h"
#include"math.h"
#include"time.h"

  clock_t start,stop;
  double duration;
  int MaxSubseqSum1(int A[],int N)
  {
    int ThisSum,MaxSum=0;
    for (int i = 0; i < N; i++) {
      for (int j = i; j < N; j++){
        ThisSum=0;
        for (int k = i; k < j; k++) {
            ThisSum+=A[k];
            if(ThisSum>MaxSum)
            MaxSum=ThisSum;
          }
      }
  }
  return MaxSum;
}

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

int MaxSubseqSum3(int A[],int N)
{
    int ThisSum,MaxSum=0;
    //分而治之
    return MaxSum;
}

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

int main()
{
  int A[]={-1,3,-2,4,-6,1,6,-1},MAX=0;
  start=clock();
  for (int i = 0; i < 99999; i++) {
      MAX=MaxSubseqSum4(A,8);
  }
  stop=clock();
  duration=((double)(stop-start)/CLK_TCK/100000);
  printf("%d\n",MAX);
  printf("%lf\n",duration);
  return 0;
}