Anson's blog
Anson
2022-12-28
目录

数据结构与算法

# 数据结构与算法

学习笔记🎉

# 引入部分

# 整个世界就是数据及其算法

  • 《未来简史》 核心观点：整个世界就是数据以及算法

  • 《三体》/ 《时间移民》--- 计算机全真模拟地球上我们现实生活 模拟时间比我们现在快一点 所以有一个人利用

# 关于‘ 计算 ‘ 的数学模型

计算机是数学家一次失败思考的产物！ 哈哈哈

  • 20世纪30年代，几位逻辑学家各自独立提出了几个关于“计算”得书序模型
# 1. 哥德尔和克莱尼的递归函数模型
# 2. 丘奇的Lambda验算模型
# 3. 波斯特的Post机模型
# 4. 图灵的图灵机模型 

######################
""" 图灵机 """
1. 1936年，Alan Turing提出一种抽象计算模型  基本思想就是用机器模拟人用纸笔运算的过程，但比数值计算更为简单
* 
2. 2014 模仿游戏
1
2
3
4
5
6
7
8
9
10
  • 研究证明，这几个关于'基于有穷观点的能行方法'的计算模型，全都是等价的
  • 虽然西伯尔特的计划最终证明无法实现
    • 不存在“能行方法”可以判定所有数学命题的额真假
    • 总有数学命题其真假是无法证明的
  • 但“能行可计算”概念成为计算机理论的基础

# 装饰器时间计算

import time

# 装饰器函数
def get_time(func):
    def inner():
        begin = time.time()
        func()
        end = time.time()
        print("函数执行花费%f" % (end-begin))
    return inner


@get_time
def func1():
    for i in range(100000):
        print(i)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 什么是数据结构、算法

# 时间复杂度

注意：我们的时间复杂度是渐进时间复杂度，所以除了 最高幂次的n 其余数都可忽略，因为只有最高幂次才具有函数变化关系的代表性

O(1): 常数最快

# 这个函数被调用的时候 从上到下就执行一次，所以就是--->O(1)
def a():
    a = 1
    b = 1
    c = a + b
1
2
3
4
5

O(logn)：对数

# 1. 以变量n和代码运行次数m得出关系式:2^m=n   
# 2. m为代码运行的次数  所以 m = logn (默认log以2位底)    所以--->O(logn)
def b(n):
    a = 1
    if a < n:
        a = a * 2
    else:
        pass
1
2
3
4
5
6
7
8
9

O(n)：线性 也就是1次函数

# 1. 以变量n和代码运行次数m得出关系式:m=n   即代码执行的次数取决于且等于n   所以--->O(n)
def c(n):
    for i in rang(n):
        print(f'Reba{i}')
1
2
3
4

O(n*logn)：对数线性 也就是对数的一次函数

def d(n):
    for i in rang(n):
        a = 1
        if a < n:
            a = a * 2
        else:
            pass
1
2
3
4
5
6
7

O(n²)：二次函数 即平方

def c(n):
    for a in range(n):
        print(f'Oyangnana{a}')
        for b in rang(n):
            print(f'Reba{b}')
1
2
3
4
5

O(n³)：三次函数 即立方函数

def c(n):
    for a in range(n):
        print(f'Oyangnana{a}')
        for b in rang(n):
            print(f'Reba{b}')
            for c in rang(n):
                print(f'nazha{c}')
1
2
3
4
5
6
7

O(n^n)：三次函数 即指数函数

# pass
1

# 空间复杂度

本质上就是一个变量会不会随着时间的变化自己的占用内存空间也会发生变化

O(1)

a = 1
b = 2
c = 3
a += 1
1
2
3
4

O(n)

a = 1
while a < n:
    a += 1
1
2
3

O(n^2)

# 暂时还没有例子
1

# 常见计算

累加计算、变位词的判断问题、待增加

# ====== 0. 计算运行时间 =======
start = time.time()
end = time.time()

# ================== 1. 1到n的累加 ===================
# （1）o(n)   常规思路 n = n + 1        
def sum0fN1(n):
    start = time.time()
	theSum = 0
    for i in range(1,n+1):
        theSum = theSum+i
    end = time.time()
    return theSum, end-start
# (2) o(1)   求和公式 sum = (n*(n+1))/2
def sum0fN2(n):
    start = time.time()
    theSum = (n*(n+1))/2
    end = time.time()
    return theSum,end-start

for i in range(5):
	print('Sum is %d required %10.7 seconds' % sum0fN1(1000))
    

# =================== 2. 变位词判断 ==================

(1) 遍历思路
def anagramSolution1(s1, s2):
    """
    O(n²)
    """
    # 跳出来看这个问题 
    # 思路是把变换前的字符放到列表  变化后的遍历列表内容
    # 判断结束条件 1.列表内容为找到即打钩为None或者第1个就没找到  2.结果是否为真
    # 对字符串进行强制类型转化为列表 目的是为了给找到的元素打标志位
    start = time.time()
    s2 = list(s2)
    # s1遍历下标
    pos1 = 0
    # 结果标志
    stillOk = True
    while pos1<len(s1) and stillOk:
        pos2 = 0
        found = False
        while pos2 < len(s2) and not found:
            if s1[pos1] == s2[pos2]:
                found = True
            else:
                pos2 = pos2 + 1
        if found:
            # 如果没有这一步其实也可以
            s2[pos2] = None
            # pass
        else:
            stillOk = False
        pos1 = pos1 + 1
    print(s2)
    end = time.time()
    return stillOk, end-start

(2) 排序思路
def anagramSolution2(s1, s2):
    # 这个方法比较便利 直接把两个字符串排好序  每个对应下标对比即可
    """
    O(nlogn)

    sort 方法简介：list.sort(cmp=None, key=None, reverse=False)：
        cmp -- 可选参数, 如果指定了该参数会使用该参数的方法进行排序。
        key -- 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对				象中的一个元素来进行排序。
        reverse -- 排序规则，reverse = True 降序， reverse = False 升序（默认）
    """
    start = time.time()
    alist1 = list(s1)
    alist2 = list(s2)

    alist1.sort()
    alist2.sort()

    pos = 0
    matches = True
    while pos < len(s1) and matches:
        if alist1[pos] == alist2[pos]:
            pos = pos + 1
        else:
            matches = False
    end = time.time()
    return matches, end-start

(3) 计数思路
def anagramSolution3(s1, s2):
    """ 
    O(n^n)
    
    计数比较: 把每个字符串计算个数，判断数量即可

    ord 方法简介：以一个字符（长度为1的字符串）作为参数，返回对应的 ASCII 数值，或者 Unicode 数值
        ord('a')   97

    注意：这个解法中有一个问题，就是不能写字母外的符号，否则将会列表下标溢出！！！！！！
     """
    start = time.time()
    # 列表的一种添加同一个元素的快捷方法
    c1 = [0]*26
    c2 = [0]*26
    print(c1)
    # 1. 计数部分
    for i in range(len(s1)):
        # 计算出s1字符串中第i位的 ASCII值 和 a 字符 ASCII 做差值
        # 为什么不直接用原有字符的 ASCII 呢？
        pos = ord(s1[i])-ord('a')
        # 做完差值的pos数值如果是固定的则意味着是同一个字符出现多次
        # 则在C1列表中对应的位置+1计数
        c1[pos] = c1[pos] + 1
    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] = c2[pos] + 1
    j = 0
    stillOk = True
    # 2. 计数器也就是两个列表的比较
    while j < 26 and stillOk:
        if c1[j] == c2[j]:
            j = j + 1
        else:
            stillOk = False
    end = time.time()
    return stillOk,end-start

s1 = 'qwertyuiopasdfghjklzxcvbnm'
s2 = 'mnbvcxzlkjhgfdsapoiuytrewq'
anagramSolution3(s1,s2)
print('结果是：%d, 用时：%10.9f s' % anagramSolution3(s1,s2))
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

# 链表

# 有序链表

线性结构是一种有序数据项的集合，其中每个数据项都有唯一的前驱和后继

线性结构包括：顺序表(即Python中的列表)、栈、队列

  • 定义：有序表是一种数据项依照某个可比性质（如整数有大小、字母有先后）来决定在列表中的位置
  • 注意：数据项的相对位置，取决于他们之间的“大小”比较 所以，由于Python的扩展性，对数据项的讨论并不仅适用整数，可适用于所有**定义了__gt__方法(即‘>'操作符')的数据类型)**的数据类型！

# 无序链表

# 栈&队列

# 栈

# =================== 0. 栈的创建 ====================
class Stack:
    def __init__(self) -> None:
        """ 空列表代替栈本身 """
        self.items = []

    def isEmpty(self):
        """ 判断是否为空栈 """
        return self.items == []

    def push(self,item):
        """ 
        入栈添加元素 
        append 直接往末尾添加
        
        """
        self.items.append(item)
        # self.items.insert(0,item)

    def pop(self):
        """ 
        出栈  
        pop: 可自定义删除元素下标 并返回对应元素值
        
        """
        return self.items.pop()
        # return self.items.pop(0)
    
    def peek(self):
        """
        查找元素最后一位
        """
        return self.items[len(self.items)-1]
        # return self.items[0]

    def size(self):
        return len(self.items)
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
27
28
29
30
31
32
33
34
35
36
37

# 队列

# ==================== 0. 队列的创建 =========================
1
2

# 双端队列

# ===================== 0. 双端队列的创建 ===================
1
2

# 排序&查找

# 排序

# 冒泡排序

o(n²) 优化后还是o(n²) 但是减少了无效的交换对比

# 选择排序

# 插入排序

# 谢尔菲排序

# 归并排序

# 快速排序
1

# 查找

# 顺序查找

# 二分查找

# 递归&动态规划

# 树

# 图
1
上次更新: 2022/12/28, 07:42:52
技术文档
复盘思路

← 复盘思路→

最近更新
01
12月阳性过程记录
12-15
02
ZKZH-智龙微课硬件开发笔记
12-09
03
原神文案
12-08
更多文章>
Theme by Vdoing | Copyright © 2022-2022 Anson Pei | MIT License