数据结构和算法（1）

一、数据结构的组成方式

算法的本质是一系列程序指令，用于解决特定的运算和逻辑问题。数据结构是数据的组织、管理和存储格式，其使用目的是高效地访问和修改数据。

1.线性结构

　　线性结构是最简单的数据结构，包括数组、链表，以及由它们衍生出来的栈、队列、哈希表。

2.树

　　树是相对复杂的数据结构，其中比较有代表性的是二叉树，由它又衍生出了二叉堆之类的数据结构。

3.图

　　图是更为复杂的数据结构，因为在图中会呈现出多对多的关联关系。

4.其他数据结构

　　除上述所列的几种基本数据结构以外，还有一些其他的千奇百怪的数据结构。它们由基本数据结构变形而来，用于解决某些特定问题，如跳表、哈希链表、位图等。

二、时间复杂度和空间复杂度

衡量算法的好坏有很多标准，其中最重要的两大标准是算法的时间复杂度和空间复杂度。简单来说，时间复杂度是执行算法的时间成本，

1. 4种程序基本操作执行次数

场景1　给小明1个长度为10cm的面包，小明每3分钟吃掉1cm，那么吃掉整个面包需要多久？

T （n）=3n，执行次数是线性的。

1 def eat1(n):
2     for i in range(n):
3         print("等待1min")
4         print("等待1min")
5         print("吃1cm面包")

场景2 　给小明1个长度为16cm的面包，小明每5分钟吃掉面包剩余长度的一半，即第5分钟吃掉8cm，第10分钟吃掉4cm，第15分钟吃掉
2cm……那么小明把面包吃得只剩1cm，需要多久呢？

T （n）=5logn，执行次数是用对数计算的。

def eat2(n):
    while n > 1:
        print("等待1min")
        print("等待1min")
        print("等待1min")
        print("等待1min")
        print("吃一半面包")
        n /= 2

场景3 　给小明1个长度为10cm的面包和1个鸡腿，小明每2分钟吃掉1个鸡腿。那么小明吃掉整个鸡腿需要多久呢？

T （n）=2，执行次数是常量。

def eat3(n):
    print("等待1min")
    print("吃一个鸡腿")

场景4 　给小明1个长度为10cm的面包，小明吃掉第1个1cm需要1分钟，吃掉第2个1cm需要2分钟，吃掉第3个1cm需要3分钟……每吃
1cm所花的时间就比吃上一个1cm多用1分钟。那么小明吃掉整个面包需要多久呢？

T （n）=0.5n² +0.5n，执行次数是用 多项式 计算的。

def eat4(n):
    for i in range(n):
        for j in range(i):
            print("等待1min")
        print("吃1cm面包")

2. 渐进时间复杂度

官方定义：若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f （n）是T（n）的同数量级函数。记作T（n）= O（f（n）），称为O（f（n）），O为算法的渐进时间复杂度，简称为时间复杂度。

直白来讲，时间复杂度就是把程序的相对执行时间函数T（n）简化为一个数量级，这个数量级可以是n 、n² 、n³ 等。

如何推导出时间复杂度呢？有如下几个原则：

如果运行时间是常数量级，则用常数1表示。
只保留时间函数中的最高阶项。
如果最高阶项存在，则省去最高阶项前面的系数。

回头看看刚才的4个场景。

场景1 T(n)=3n，最高阶项为3n，省去系数3，则转化的时间复杂度为：T(n)=O(n) 。

场景2 T(n)=5logn，最高阶项为5logn，省去系数5，则转化的时间复杂度为：T(n)=O(logn) 。

场景3 T(n)=2，只有常数量级，则转化的时间复杂度为：T(n)=O(1)。

场景4 T(n)=0.5n² +0.5n ，最高阶项为0.5n²，省去系数0.5，则转化的时间复杂度为：T(n)=O(n²)。

当n的取值足够大时，不难得出：O(1)2)

3. 空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，它同样使用了大O表示法。程序占用空间大小的计算公式记作 S（n）= O（f（n）），其中n为问题的规模，f（n）为算法所占存储空间的函数。

常量空间

　当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作 O（1）。如：

def fun1(n):
    i = 3
    # do something

线性空间

　当算法分配的空间是一个线性的集合（如列表），并且集合大小和输入规模n 成正比时，空间复杂度记作 O（n）。如：

def fun2(n):
    array = [[0] * n]
    # do something

二维空间

　当算法分配的空间是一个二维列表集合，并且集合的长度和宽度都与输入规模n 成正比时，空间复杂度记作 O（n²）。如：

def fun3(n):
    matrix = [[0] * n] * n
    # do something

递归空间

　执行递归操作所需要的内存空间和递归的深度成正比，纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O（n）。如：

def fun4(n):
    if n > 0:
        fun4(n-1)
    # do something

算法和数据结构

数据结构和算法（1）

相关

标签