转载

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

数据类型

数据类型是指具有预定值的一个集合,典型的数据类型有整数、浮点数、字符、字符串等等... 在计算机内存中全是由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分钟, 就行了。对于算法也是一样的。

时间复杂度

常见的时间复杂度

img

时间复杂度三种情况

一个算法有上界($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)

正文到此结束