算法与数据结构

算法：算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每个指令表示⼀个或多个操作。

算法设计要求：（正确性，可读性，健壮性，时间效率高，存储量低）

1.数据结构

数据结构：数据----->数据对象----->数据元素----->数据项

2.数据分类

一.逻辑结构划分

(1).集合结构

(2).线性结构

(3).树形结构

(4).图形结构

二.物理结构

(1).顺序存储结构

(2).链式存储结构

3.数据结构和算法关系

image

3.数据结构------常见的时间复杂度（大O表示法）

image

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式：S(n) = n(f(n))其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数

举例

1.常数阶时间复杂度计算O(1)

3 O(1)

void testSum1(int n){

        int sum = 0;                             //执行一次

        sum = (1+n)/2;                         //执行一次

        printf("testSum1:%d\n",sum);   //执行一次

}

//7次 O(1)

void testSUm2(int n){

    int sum = 0;//执行一次

    sum = (1+n)*n/2;//执行一次

    sum = (1+n)*n/2;//执行一次

    sum = (1+n)*n/2;//执行一次

    sum = (1+n)*n/2;//执行一次

    sum = (1+n)*n/2;//执行一次

    printf("testSum2:%d\n",sum);   //执行一次

}

//x=x+1; 执行一次 O(1)

void add(int x){

    x = x+1;

}

2.线性阶时间复杂度计算O(n)

void add2(int x, int n){

    int i, sum = 0; //执行1次

    for (i=1; i <=n; i++){ //执行n+1次

        sum += i; //执行n次

    }

    printf("testSum3:%d\n",sum); //执行1次

}

3.对数阶时间复杂度计算O(logn)

//2的x次方等于n x = log2n -> logn
void testA(int n){
  int count = 1; //执行1次
  while (count < n){
    count = count * 2;
  }
}

3.平方阶时间复杂度计算O(n^2)

void add3(int x, int y){
  for (int i = 0; i < n; i++){  //执行n次
    for(int j = 0; j < n; j++){ //执行n次
      x = x +1;
    }
  }
}

//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2+ n/2 = O(n^2)
void add3(int x, int y){
  for (int i = 0; i < n; i++){  //执行n次
    for(int j = i; j < n; j++){ //执行n次
      x = x +1;
    }
  }
}