Hello Algorithm:Capture 1,2 初识算法
大家好 :) 自学完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)
给大家留个小思考,计算下时空复杂度 :), 当然我写在上面了,可以思考一下为什么。
困了,今天就学到这,晚安~
原文地址:https://blog.csdn.net/m0_62716099/article/details/142580371
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!