数据结构和时间复杂度简单入门

数据类型

数据类型是指具有预定值的一个集合，典型的数据类型有整数、浮点数、字符、字符串等等... 在计算机内存中全是由0和1填充，比如整数数据类型占2个字节(具体看编译器), 浮点数(float)占4个字节, 所以在内存中把两个字节组合起来(16位)可以成为整数, 4个字节组合起来(32位)为浮点数, 数据类型分为两种。

编程语言定义的数据类型(基本数据类型)
用户定义的数据类型

以Java为例, 基本的数据类型有8种。

boolean (布尔类型, 用于判断) (true false)
byte (8位有符号整数)(最小值-128,最大值127)
short (16位有符号整数)(最小值-32768, 最大值32767)
int (32位有符号整数)(最小值-2147483648 (-2^31), 最大值2147483647 (2^31-1))
long (64位有符号整数)(最小值-2^63 最大值2^63-1)
float (32位浮点数)(1.4E-45~3.4028235E38)
double (64位浮点数)(4.9E-324~1.7976931348623157E308)
char (16位Unicode字符)

用户定义的数据类型

C/C 的结构体, Java的类

Java写法
    public class Dog 
    { 
        byte age; 
        int birthday; 
    }

数据结构

数据结构是计算机中存储和组织数据的一种特定方式, 常用的数据结构有数组, 字符串, 链表, 栈, 队列, 树和图等。

根据元素的组织方式, 可以分为两种。 线性结构 非线性结构

线性结构

可以按线性次数访问元素,是一个有序的数据集合, 不强制所有的元素连续存储在一起, 典型的线性结构数组链表栈队列

非线性结构

每个元素不再保持在一个线性序列中, 以非线性的次序来存储访问, 典型的非线性结构 ***数组(包括二维数组) 图 * 树

什么是算法？

算法简单的来说，就是一个有限的步骤，比如把大象塞进冰箱里需要几步？3步就行了，打开冰箱，把大象塞进去，关上冰箱。(这里不考虑冰箱大小和大象体积)，这就是一个算法。

算法的特征有5个 输入性 : 一个算法必须有>=0的数量 输出性 : 一个算法应该有>=1的输出计算结果 正确性 : 描述算法的步骤必须没有歧义，保证算法的输出性是符合算法要求的。 有限性 : 代码的执行语句序列是有限的 * 有效性/可行性 : 能够实现以上步骤

就像上面的大象例子，要求是把大象塞进冰箱里，所以输入就是把大象塞进去的过程，输出就是大象在冰箱里的结果。

总结起来就是说，算法其实是一条接一条的指令来解决给定的问题。

算法分析

一个问题可能有n个解, 而算法分析则是在n个解中寻找最优解，举个例子, 从南昌到苏州, 可以坐高铁, 可以坐火车, 可以自己开车 , 从附件城市转车, 如果你愿意的话甚至可以走路, 明显最优解是坐高铁，只要4小时13分钟, 就行了。对于算法也是一样的。

时间复杂度

常见的时间复杂度

时间复杂度三种情况

一个算法有上界($O$), 下界($\Omega$), 平均时间($\Theta$), 如果上界和下界一样, 就需要用$\Theta$表示。

例子

循环: 循环体内的语句运行时间(包括循环条件的判断)是和迭代次数相乘, 从内向外分析, 时间是所有所有循环规模的乘积, 算法分析中忽略低项。

//循环执行n次
for(int i = 1; i<=n; i  )
{
    int m = m 2; //时间常数c
}

时间为: c*n = cn = O(n)

ex2

//循环了n次
for(int i = 1; i<=n; i  )
{
    //循环了n次
    for(int j = 1; j<=n; j  )
    {
        int m = m 2; //常数时间c
    }
}

时间: c nn = c*n² = (n²)

if-then-else 条件语句: 最坏情况下的运行时间是: 条件判断时间最大值(then运行时间或else运行时间)

ex1

int a = 10;
// 时间复杂度是O(n)
if(a == 10) //条件常数c
{
    //循环了n次 
    for(int i = 0; i<a; i  )
    {
        System.out.println(i); //常数c
    }
}
else 时间复杂度O(1)
{
        System.out.println(a); //常数c
}

所以这里的时间复杂度是O(n)