type
status
date
slug
summary
tags
category
icon
password
算法
算法是指对特定问题求解步骤的一种描述。
它不依赖于任何一种语言,既可以用自然语言、程序设计语言(C、C++、Java、Python等)描述,也可以用流程图、框图来表示。采用伪代码来描述算法,“伪代码”介于自然语言和程序设计语言之间,它更符合人们的表达方式,容易理解,但不是严格的程序设计语言。
算法特性
- 有穷性:算法是由若干条指令组成的有穷序列,总是在执行若干次后结束,不可能永不停止。
- 确定性:每条语句有确定的含义,无歧义。
- 可行性:算法在当前环境条件下可以通过有限次运算实现。
- 输入输出:有零个或多个输入,一个或多个输出。
好的算法标准
- 正确性 算法能够满足具体问题的需求,程序运行正常,无语法错误,能够通过典型的软件测试,达到预期的需求。
- 易读性 算法遵循标识符命名规则,简洁易懂,注释语句恰当适量,方便自己和他人阅读,便于后期调试和修改。
- 健壮性 算法对于非法数据和操作应该有较好的反映和处理。
- 高效性 高效性是指算法运行效率高,即算法运行所消耗的时间短。
- 低存储性 低存储性是指算法所需要的存储空间低。
时间复杂度
时间复杂度:算法运行需要的时间,一般将算法的执行次数作为时间复杂度的度量标准。
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F87cd7b33-b48f-404a-8322-8403322877a9%2F1a6a1709-72ad-4a45-a402-1f7a92db8936%2FUntitled.png?table=block&id=5edd7034-18c6-4d1c-82b2-58a4ee003d0b&t=5edd7034-18c6-4d1c-82b2-58a4ee003d0b&width=1139&cache=v2)
时间复杂度:渐进上界(最坏情况),渐进下界(最好情况),渐进精确界(逼近的方式).
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F87cd7b33-b48f-404a-8322-8403322877a9%2F46f0c826-3d49-4f1c-90ba-ee1a7e16a9a6%2FUntitled.png?table=block&id=ac3bcd78-598e-44d3-a49f-8c45d9479330&t=ac3bcd78-598e-44d3-a49f-8c45d9479330&width=1002&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F87cd7b33-b48f-404a-8322-8403322877a9%2Fc2824f6b-51b5-4e83-9a4f-9eb0b85335cc%2FUntitled.png?table=block&id=d3e6ef1c-dd30-47c3-a9bf-5bb7b36f8ec8&t=d3e6ef1c-dd30-47c3-a9bf-5bb7b36f8ec8&width=368&cache=v2)
不是每个算法都能直接计算次数。
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F87cd7b33-b48f-404a-8322-8403322877a9%2F145b05a3-b1fa-4321-80b9-eada00f4e5c6%2FUntitled.png?table=block&id=0b0925f4-53d0-4b8b-a4e4-4c73ed0e9446&t=0b0925f4-53d0-4b8b-a4e4-4c73ed0e9446&width=1147&cache=v2)
在计算任何算法的时间复杂度时,可以忽略所有低次幂和最高次幂的系数,这样能够简化算法分析。
空间复杂度
空间复杂度:算法占用的空间大小。一般将算法的辅助空间作为衡量空间复杂度的标准。
算法占用的存储空间
- 输入,输出数据;(一般不计算)
- 算法本身;(可忽略不计)
- 额外需要的辅助空间。
递归算法中,每一次递推需要一个栈空间来保存调用记录,因此,空间复杂度需要计算递归栈的辅助空间。
递归包括递推和回归。
递推是将原问题不断分解成子问题,直到达到结束条件,返回最近子问题的解;然后逆向逐一回归,最终到达递推开始的原问题,返回原问题的解。
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F87cd7b33-b48f-404a-8322-8403322877a9%2F2f9bf3f9-7312-464a-83f2-97e70ff68058%2FUntitled.png?table=block&id=fd8a1b1a-261f-44ed-a069-7ec00b22af72&t=fd8a1b1a-261f-44ed-a069-7ec00b22af72&width=940&cache=v2)
栈 ,后进先出.
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F87cd7b33-b48f-404a-8322-8403322877a9%2Fc3e5eb49-ba2c-4e5e-8c96-0868449f5a8c%2FUntitled.png?table=block&id=25ffb9b1-59a6-4b46-a981-8745e584b80e&t=25ffb9b1-59a6-4b46-a981-8745e584b80e&width=844&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F87cd7b33-b48f-404a-8322-8403322877a9%2Fd384dc5d-5ef0-4061-94f1-da04b719b089%2FUntitled.png?table=block&id=b4121d0d-50f9-4f08-88b6-06f82590e998&t=b4121d0d-50f9-4f08-88b6-06f82590e998&width=828&cache=v2)
在运算过程中,使用了n个栈空间作为辅助空间,因此将阶乘递归算法的空间复杂度为O(n),时间复杂度也为O(n).
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F87cd7b33-b48f-404a-8322-8403322877a9%2F2beff6c0-f219-47a6-af41-f8c592cd14d9%2FUntitled.png?table=block&id=b3fd14b4-0f2d-4f2b-8203-82a2aed903cb&t=b3fd14b4-0f2d-4f2b-8203-82a2aed903cb&width=554&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F87cd7b33-b48f-404a-8322-8403322877a9%2F85b6e0c4-d966-470b-a5ae-19b5ed845e11%2FUntitled.png?table=block&id=402f5286-c577-4cd8-9083-022005b58976&t=402f5286-c577-4cd8-9083-022005b58976&width=909&cache=v2)
有关算法相关方面的问题,欢迎您在底部评论区留言,一起交流~
- 作者:Nolan
- 链接:https://nolanblog.top/article/day1
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。