概念

计算机世界著名公式，由瑞士计算机科学家尼克劳斯·威茨（Niklaus Wirth）提出

程序 = 数据结构 + 算法

数据结构

定义

计算机存储组织数据的方式

算法

定义

解决特定问题的求解步骤

特性

输入有零个或多个输入
输出至少有一个或多个输出
有穷性
确定性
可行性

算法的时间复杂度和空间复杂度

时间复杂度计算算法所需要的时间采用大O 表示法

常数阶 O(1)
平方阶 O(n 2)
立方阶 O(n 3)
线性阶 O(n)

例
list 的复杂度
- append 0(1)
- pop() O(1)
- pop(i) O(n)
- sort O(n log n)
- reverse O(n)
dict 的时间复杂度
- copy O(n)
- Delete O(1)
空间复杂度计算算法所需要的内存

线性表

定义：具有零个或多个数据元素的有限序列

特征

第一个元素没有前驱元素
最后一个元素没有后继元素
其他元素只有一个前驱和一个后继

操作：插入删除查找
分类：顺序表链表

顺序表

定义

在计算机内存中以一组地址的存储单元依次存储数据元素的线性结构

插入删除最好的时间复杂度O(1) 最坏的时间复杂度 O(n)
查找时间复杂度为 O(1)

特点：

优点：支持随机访问
缺点：插入和删除需要移动大量元素会造成空间碎片

适合场景

读取数据的时候 python中的 list tuple

链表

定义

是一种基础数据结构是一种线性表

分类

单向链表

有俩个域一个是链接域(下一个节点的地址) 一个是信息域(存放的是数据)
单向循环链表

最后一个节点的指针域指向第一个节点
双向链表

俩个指针域一个元素域

数据结构与算法作用

没有看过数据结构和算法，有时间对问题可能会没有任何思路，不知如何下手去解决：

大部分时间可能解决了问题，可是对程序运行的效率和开销没有意识，性能下降；
有时会借助别人开发的利器暂时解决了问题，可是遇到了性能瓶颈的时候，又不知道该如何进行针对性优化。

按照不同的角度，
数据结构可分为
逻辑结构和物理结构。

逻辑结构：

是指数据对象中数据元素之间的相互关系。
分为四种：
集合结构、线性结构、树形结构和图形结构。

数据元素的存储结构可分为两种：
顺序存储结构和链式存储结构。

顺序存储结构：

把数据元素放在地址连续的存储单元中，
数据间的逻辑关系和物理关系一致。如，b

链式存储结构：

把数据元素放在任意的存储单元中，数据间使用指针关联。
数据元素的存储关系不能反映其逻辑关系。如，链表。

算法是解决特定问题求解步骤的描述，
在计算机中表现为指令的有限序列，
并且每条指令表示一个或多个操作。

算法的基本特性：

输入，算法具有零个或多个输入，
输出，至少有一个或多个输出。
有穷性，算法在执行有限步后能够自动结束，不会出现无限循环。
确定性，算法的每一步都具有确定的含义，不会出现二义性。
可行性，算法的每一步都能够通过执行有限次操作完成。

算法复杂度分为时间复杂度和空间复杂度。

时间复杂度是指执行算法所需要的计算工作量（时间）

空间复杂度是指执行这个算法所需要的内存空间

算法的时间复杂度””反映了算法执行的时间长短，它是度量一个算法好坏的重要指标。””
度量一个算法的时间复杂度通常采用大O表示法

时间复杂度的几条基本计算规则：

基本操作，即只有常数项，认为其时间复杂度为O(1)
顺序结构，时间复杂度按加法进行计算
循环结构，时间复杂度按乘法进行计算
分支结构，时间复杂度取最大值
判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略
在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度

# import time #引入时间模块
# def func():
#     # 时间戳  time.time()
#     start_time = time.time()
#     for i in range(0,1001):       # n*n 循环结构  +9常数项 可以忽略
#         for j in range(0,1001):
#             # s = 1000 - i - j        #顺序结构
#             for s in range(0,1001):
#                 if i ** 2 + j ** 2 + s ** 2 == s ** 2 and i + j + s ==1000 : #二次幂 + - 基本操作   分支结构 if elif
#                     print("i = %d,j = %d ,s =%d" % (i,j,s))  #可以认作基本操作
#
#     end_time = time.time()
#     print("demo 执行时间为：%f" % (end_time-start_time))  #开始到结束用了多长时间
#
# func()




# import time,timeit  #python 内置的性能测试模块
# def func():
#     for i in range(0,1001):
#         for j in range(0,1001):
#             s = 1000 - i - j
#             if i ** 2 + j ** 2 + s ** 2 == s ** 2  :
#                 print("i = %d,j = %d ,s =%d" % (i,j,s))
# if __name__ == '__main__':
#     ss = timeit.Timer("func()","from __main__ import func")
#     print(ss.timeit(5)/5)

构造栈

"""
Stack() 创建一个新的空栈
push(item) 添加一个新的元素item到栈顶
pop() 弹出栈顶元素
peek() 返回栈顶元素
is_empty() 判断栈是否为空
size() 返回栈的元素个数
"""


class Stack():
    """创建一个新的空栈类"""

    def __init__(self):
        """创建一个新的空栈"""
        self.alist = []

    def push(self, item):
        """添加一个新的元素item到栈顶"""
        self.alist.append(item)

    def pop(self):
        """弹出栈顶元素"""
        if self.alist == []:
            return None
        else:
            return self.alist.pop()

    def peek(self):
        """返回栈顶元素"""
        if self.alist == []:
            return None
        else:
            return self.alist[-1]

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

    def size(self):
        """返回栈的元素个数"""
        return len(self.alist)


if __name__ == '__main__':
    s = Stack()
    print(s.is_empty())
    print(s.size())
    s.push(1)
    s.push(2)
    s.push(3)
    s.push(4)
    s.push(5)
    print(s.size())
    print(s.pop())
    print(s.size())
    print(s.is_empty())
    print(s.peek())

进阶写法数字转二进制

class MyStack:
    def __init__(self):
        self.s = []

    def push(self, x: int) -> None:
        self.s.append(x)

    def pop(self) -> int:	
        return self.s.pop()

    def size(self) -> int:
        return len(self.s)

    def empty(self) -> bool:
        return not bool(self.s)


stack = MyStack()


def transform(num: int) -> str:
    while num != 0:
        remain = num % 2
        num = int(num / 2)
        stack.push(remain)

    s = ""
    while not stack.empty():
        s += str(stack.pop())
    return s


print(transform(13))

构造队列

"""
Queue() 创建一个空的队列
enqueue(item) 往队列中添加一个item元素
dequeue() 从队列头部删除一个元素
is_empty() 判断一个队列是否为空
size() 返回队列的大小

"""


class Queue():

    def __init__(self):
        """创建一个空的队列"""
        self.alist = []

    def enqueue(self, item):
        """往队列中添加一个item元素"""
        self.alist.append(item)

    def dequeue(self):
        """从队列头部删除一个元素"""
        if self.alist == []:
            return None
        else:
            self.alist.pop(0)

    def is_empty(self):
        """判断一个队列是否为空"""
        return self.alist == []

    def size(self):
        """返回队列的大小"""
        return len(self.alist)


if __name__ == '__main__':
    q = Queue()
    print(q.size())
    print(q.is_empty())
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    q.enqueue(5)
    q.dequeue()
    q.dequeue()
    q.dequeue()
    print(q.size())
    print(q.is_empty())

进阶写法

class MyQueue:

    def __init__(self):
        self.s = []

    def push(self, x: int) -> None:
        """
        x: int 申明类型 提高代码健壮性
        -> 返回值 为None
        """
        self.s.append(x)

    def pop(self) -> int:
        return self.s.pop(0)

    def empty(self) -> bool:
        return not bool(self.s)


myq = MyQueue()

觉得文章写的不错，可以请喝杯咖啡

Post author: 王彦翔
Post link: https://yanxiang.wang/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/
Copyright Notice: All articles in this blog are licensed under unless otherwise stated.

概念