Hello Algorithm:Capture 1,2 初识算法

时间:2024-09-30 15:53:50

        大家好 :)  自学完sklearn的基本使用后,颇感无趣。虽有阅文几篇,却无所获。遂于24年9月26日决习hello algorithm。 :)

        好了,不开玩笑了。其实开设这篇专栏我也不知道有没有什么意义。其实是因为最近在读TaskWeaver,但是源码又看不懂(当然看完了我会第一时间给大家总结的),感到头疼,所以决定摸摸鱼,继续写写自己的小博客~~~

        这个专栏主要是对网站教程的总结与代码实现,能力有限,欢迎大家一同交流讨论!

        教程网站:序 - Hello 算法

        

何为算法

        算法即是有限时间内解决问题的思路,旨在达到时间与空间上的最优,这意味着我们写代码并不局限于一种语言。但是我用python

        而数据结构则是组织和存储数据的方式,尽量占用少内存,操作尽量快速,提供简洁的数据表示。

        

复杂度分析

        简单来说,在执行的代码中,我们不仅要达到运行时间的最短,也要尽量达到最少的空间效率。实际过程考虑到硬件、数据大小、测试时间等影响,很少展开完整的测试实验,而是通过复杂度分析来进行判断

迭代

        迭代即循环,我们通过简单的案例熟悉一下基本的for, while循环。

def for_loop(n: int) -> int:
    """
    
    时间复杂度 o(n)
    空间复杂度 o(1)
    
    :param n: 
    :return:  
    """
    res = 0
    for i in range(1, n+1):
        res += i
    return res

for_loop(3) 
def while_loop(n: int) -> int:
    res = 0
    i = 1
    while i <= n:
        res += i
        i += 1
    return res

while_loop(3)

        这个代码也很简单,就是实现通过简单的循环实现一个累加。时间复杂度和空间复杂度也都是相同的。因为循环次数是与参数n相关,所以时间复杂度就是 o(n), 与其同时由于空间上只有n一个变量,那么我们的空间复杂度就是 o(1)。很简单吧!

递归

        递归主要是通过调用函数自身来解决问题。递归函数就是先一次又一次的深入到最深层,然后再从最深层一层一层的叠加结果。

def recur(n: int) -> int:
    if n == 1:
        return 1
    res = recur(n - 1)
    return n + res

recur(3)

        当然这个函数的时空复杂度怎么算呢?也还可以,调用了3次函数,每次都有一个新的n,所以时空复杂的都是o(n)

        当然递归也有不同,具体表现为如下:

  • 普通递归:当函数返回到上一层级的函数后,需要继续执行代码,因此系统需要保存上一层调用的上下文。
  • 尾递归:递归调用是函数返回前的最后一个操作,这意味着函数返回到上一层级后,无须继续执行其他操作,因此系统无须保存上一层函数的上下文。

def tail_recur(n, res):
    """尾递归"""
    # 终止条件
    if n == 0:
        return res
    # 尾递归调用
    return tail_recur(n - 1, res + n)

        当然看似某些问题十分困难,但是利用递归会非常简易进行实现。比如:

def fib(n: int) -> int:
    """
    
    时间复杂度 o(2n)
    空间复杂度 o(n)
    
    :param n: 
    :return: 
    """
    # f(n) = f(n-1) + f(n-2)
    if n == 1:
        return 0
    if n == 2:
        return 1
    
    return fib(n - 1) + fib(n - 2)

fib(5)

        给大家留个小思考,计算下时空复杂度 :), 当然我写在上面了,可以思考一下为什么。

困了,今天就学到这,晚安~