【数据结构】——入门

算法基础

算法的特性：

• 输入输出：算法具有零个或者多个输入，同时，算法具有至少一个的输出。

• 确定性：算法的每一步都具有确定的含义，无二义性

• 有穷性：每个算法需要在有穷的时间内完成

• 可行性：一个算法是可以被执行的

算法设计要求

• 正确性：能够满足预先指定的功能与性能的需求

• 健壮性：当输入数据不合法时，算法也能做出相关的处理

• 可读性：算法是可以阅读，理解和交流的

• 耗时低、占空间小：能够更少的使用时间和空间达成我们的目标

数据结构基础

基本概念

• 数据：信息载体

• 数据元素：数描述数据的基本单元，一个数据元素有若干个数据项组成

• 数据项：是描述数据的最小单位

• 数据对象：性质相同的一类数据元素的集合，是数据的一个子集

• 数据结构：指数据和关系的集合

四大逻辑结构

• 集合结构：所有数据元素除了同属于一个集合外

• 显性结构

• 树形结构

• 图形结构

复杂程度

时间、空间复杂度定义

• 时间复杂度
  时间复杂度表示一个程序运行所需要的时间，但是我们并不需要一个具体的时间，而是时间频度T（n），n称为问题的规模

• 空间复杂度
  空间复杂度是指运行完一个程序所需内存的大小，包括：固定部分、可变部分

  • 固定部分:
    指令空间（代码空间）、数据空间（常量、变量）等，数据静态空间

  • 可变部分：
    主要包括动态分配的空间、递归堆栈的空间

度量时间复杂度

以下为一些常用的基本公式：

a)O(a）=O(1)      其中a为常数
b)O(an)=O(n)     其中a为常数
c)O(an2++bn+c)=O(n2)  

时间复杂度O(1)示例：

#include<stdio.h>
int main(){
    printf("Hello World");  //执行一次
    return 0;       //执行一次
}

对于如上代码，执行了两次，即O(2)=O(1)，我们可以称其时间复杂度为O(1)

时间复杂度O(n)示例：

#include<stdio.h>
int main(){
    int n=10000,ans=0;  //执行一次
    for(int i=0;i<n;i++){   //执行n次
        ans+=i;     //执行一次
    }
    return 0;       //执行一次
}

我们一共执行了n*1+2次，即O(n*1+2)，由上文我们的公式得到其复杂度为O(n)

时间复杂度O(n^2)示例：

#include<stdio.h>
int main(){
    int n=10000,ans=0;  //执行一次
    for(int i=0;i<n;i++){   //执行n次
        for(int j=0;j<n;j++){   //执行n次
            ans+=j;
        }
    }
    return 0;       //执行一次
}

我们一共执行了n*n*1+2次，即O(n*n*1+2)，由上文我们的公式得到其复杂度为O(n^2)

时间复杂度O(logn)示例：

#include<stdio.h>
int main(){
    int i=1,n=10000;    //执行一次
    while(i<=n){    //执行logn次
        i*=2;
    }
    return 0;       //执行一次
}

其i的增长是倍增的形式，也就是说i会随着运行次数的增加变大的趋势变更大，这样的代码时间复杂度一般为log级别O(logn)

时间复杂度O(n*logn)示例：

#include<stdio.h>
int main(){
    int n=10000,ans=0;  //执行一次
    for(int i=0;i<n;i++){   //执行n次
        int j=0;        //执行1次
        while(j<=n){    //执行log(n)次
            j*=2;
        }
    }
    return 0;       //执行一次
}

这就是对对数级别复杂度进行嵌套，O(n*logn)级别