算法的基本概念
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法的基本概念,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1169字,纯文字阅读大概需要2分钟。
内容图文
1. 算法概念
algorithm:一个计算过程,解决问题的方法
程序设计=数据结构+算法
输入→算法→输出
数据结构就是关系
2. 时间复杂度
用来估计算法运行时间的一个式子,一般来说时间复杂度高的算法比复杂度低的算法慢
2.1 一些例子:
print('hello') # O1
for i in range(n): # O(n)
print('hello')
for i in range(n): # O(n2)
for j in range(n):
print('hello')
while n > 1: # O(logn)
print(n)
n = n//2
2.2 时间复杂度排序
2.3 快速判断算法复杂度
- 确定问题规模n
- 是否循环减半→logn
- k层关于n的循环→n^k
3. 空间复杂度
用来评估算法内存占用大小的式子
- 算法使用了几个变量:O(1)
- 算法使用了长度为n的一维列表:O(n)
- 算法使用了m行n列的二维列表:O(mn)
可以用空间换时间
4. 递归
递归的两个特点
- 调用自身
- 结束条件
def func1(x):
if x > 0:
print(x)
func1(x - 1)
# 3 2 1
def func2(x):
if x > 0:
func2(x - 1)
print(x)
# 1 2 3
对上述结果的解释
- func1的执行顺序,窄的表示打印,宽的表示函数
先打印在调用自身,从上到下执行下来 - func2的执行顺序,窄的表示打印,宽的表示函数
函数还是从上往下执行,每一层都是先递归后打印,先打印的是最里面那层递归
5. 汉诺塔问题
5.1 问题分析
- n=2时
- 小圆盘从A移动到B
- 大圆盘从A移动到C
- 小圆盘从B移动到C
- n时候,上面n-1个盘子看成一个整体
- 把n-1个盘子从A经过C移动到B
- 把n个盘子从A移动到C
- 把n-1个盘子从B经过A移动到C
def hanoi(n, a, b, c):
'''
一共n层,盘子从a经过b移动到c
'''
if n > 0:
hanoi(n - 1, a, c, b)
print('moving from %s to %s' % (a, c))
hanoi(n - 1, b, a, c)
hanoi(3,'A','B','C')
'''
moving from A to C
moving from A to B
moving from C to B
moving from A to C
moving from B to A
moving from B to C
moving from A to C
'''
原文:https://www.cnblogs.com/qiuyicheng/p/10749958.html
内容总结
以上是互联网集市为您收集整理的算法的基本概念全部内容,希望文章能够帮你解决算法的基本概念所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。