数据结构第一讲:基本概念

在线课程 MOOC浙江大学数据结构课程

1.1 什么是数据结构

书架放书

需要解决

  1. 新书插入
  2. 查找某本书的问题

方法:

  1. 随机按顺序放
    • 插入很简单,直接放最后
    • 查找很困难,一本一本找
  2. 按书名拼音顺序放
    • 插入困难,需要把所有拼音顺序在之后的书都后移
    • 二分查找
  3. 先分类,在按拼音顺序放
    • 小范围的插入和查找同上
    • 需要选择合适的类别数,太大则归类困难

打印数列

给定一个数N,一次打印从1到N.

方法:

  1. 遍历打印

    1
    2
    3
    4
    5
    6
    7
    def f1(n):
    for i in range(1, n+1):
    print(i)
    return

    print('f1-------')
    f1(10)
  2. 递归打印

    1
    2
    3
    4
    5
    6
    7
    8
    def f2(n):
    if n > 1:
    f2(n-1)
    print(n)
    return

    print('f2-------')
    f2(10)

看起来递归更加简洁,但是当n过大时,会挤爆空间!

多项式计算

程序实现
$$
f(x) = a_0 + a_1x + a_2x^2 + … + a_nx^n
$$
方法:

  1. 简单实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def f1(x, n, a=None):
    if a is None:
    return
    y = a[0]
    for i in range(n):
    y += a[i+1] * x**(i+1)
    return y

    f1(2, 3,[1,2,3,4])
  2. 递归
    $$
    f(x) = a_0 + x(a_1 + x(…(a_{n-1} + x(a_n))…))
    $$

1
2
3
4
5
6
7
8
9
def f2(x, n, a=None):
if a is None:
return
y = a[-1]
for i in range(n, 0, -1):
y = y * x + a[i-1]
return y

f2(2, 3,[1,2,3,4])

加减法不耗资源,主要考虑乘除法的元素次数。

方法1做了$n + (1+2+…+(n-1)) = (n^2 + n)/2$次乘法运算

方法2做了n次乘法运算

优劣立现!

什么是数据结构

数据对象在计算机中的组织方式

  • 逻辑结构
  • 物理存储结构

抽象数据类型

  • 数据对象集
  • 操作集

1.2 什么是算法

  • 空间复杂度S(n)
  • 时间复杂度T(n)

1.3 最大子列和问题

问题:
$$
给定N个整数的序列{A_1, A_2, …, A_N},求函数f(i, j) = \max{\{0,\sum_{k=i}^j A_k\}}的最大值
$$

方法:

  1. 暴力破解

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def f1(a):
    s = 0
    inds1 = -1
    inds2 = -1
    for i in range(len(a)):
    for j in range(i, len(a)):
    t = 0
    # t = sum(a[i:j+1])
    for k in range(i, j+1):
    t += a[k]
    if t >= s:
    s = t
    inds1 = i
    inds2 = j
    return s, inds1, inds2

    f1([1,5,-6,7,2,-3,-4,8,-9,2])

    一开始使用sum函数,误以为时间复杂度是$O(n^2)$,其实sum本身也有复杂度,真实复杂度是$O(n^3)$。不要过度依赖函数,要看计算本质!

  1. 暴力破解优化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def f2(a):
    s = 0
    inds1 = -1
    inds2 = -1
    for i in range(len(a)):
    t = 0
    for j in range(i, len(a)):
    t += a[j]
    if t >= s:
    s = t
    inds1 = i
    inds2 = j
    return s, inds1, inds2

    f2([1,5,-6,7,2,-3,-4,8,-9,2])

    时间复杂度$O(n^2)$

  1. 分而治之

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    def f3_0(a, l, u):
    if l > u:
    return 0
    if l == u:
    return max(a[l], 0)
    mid = (l + u) // 2
    lmax = s = 0
    for i in range(mid, l-1, -1):
    s += a[i]
    lmax = max(lmax, s)
    rmax = s = 0
    for i in range(mid+1, u+1):
    s += a[i]
    rmax = max(rmax, s)
    return max(lmax+rmax, f3_0(a, l, mid), f3_0(a, mid+1, u))

    def f3(a):
    return f3_0(a, 0, len(a)-1)

    # 求三个数最大值方法
    def getmax(x, y, z):
    if (x >= y) & (x >= z):
    return x
    return getmax(y, z, x)

    f3([1,5,-6,7,2,-3,-4,8,-9,2])

  1. 在线处理

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def f4(a):
    s = 0
    t = 0
    inds1 = -1
    inds2 = -1
    for i in range(len(a)):
    t = t + a[i]
    if t >= s:
    s = t
    if inds1 == -1:
    inds1 = i
    inds2 = i
    elif t > 0:
    continue
    else:
    t = 0
    inds1 = -1
    return s, inds1, inds2

    f4([1,5,-6,7,2,-3,-4,8,-9,2])

    在线处理的逻辑核心其实是一种链式增强的传播效应。

    用索引指代对应的数,符号指代其正负(e.g. (0)+表示第一位为正数)。当(0)+,(0+1)+,那么必然有(0+1+2)>=(1+2)。

注意循环的边界,什么时候j+1,什么时候不要。从i开始还是i+1开始。

需要注意细节处理,条件是否取等号影响到是否取到的是最短子列,以上实现取到的都是最后出现的最短子列。