数据结构&算法（二）_算法基础之前传（递归、时间复杂度、空间复杂度、二分查找）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构&算法（二）_算法基础之前传（递归、时间复杂度、空间复杂度、二分查找），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1925字，纯文字阅读大概需要3分钟。
内容图文
什么是算法：
间而言之算法（Algorithm）：一个计算过程，解决问题的方法
递归的两个特点：
- 调用自身
- 结束条件
递归示例：
def func(x):
if x==0:
print("我的小鲤鱼",end=‘‘)
else:
print("抱着",end=‘‘)
func(x-1)
print("的我",end="")
func(5)
‘‘‘
1
1
2
3
5
8
13
21
34
输出长度为 n 的斐波那契数列
‘‘‘
#方式一：while 循环
def fibo(num):
a=1
b=1
i=1while i<=num:
print(a,end="")
a,b = b,a+b
i+=1
# fibo(10)
#方式二：用递归函数方式
#输出某一项
def fibo2(num):
if num == 1 or num==2:
return1
elif num>2:
return fibo2(num-1)+fibo2(num-2)
#s输出整个数列
# for i in range(1,11):
# print(fibo2(i),end="")
#方式三
def fibo3(a,b,num):
if a > num:
return
print(a,end="")
fibo3(b,a+b,num)
fibo3(1,1,1100)
时间复杂度
空间复杂度
空间复杂度：用来评估算法内存占用大小的一个式子
二分查找
思路：
从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。
二分查找适合有序列表 时间复杂度 O(logn)
#!/usr/bin/env python
# -*- coding:utf-8 -*-
‘‘‘
二分查找适合有序列表
时间复杂度 O(logn)
‘‘‘
def bin_search(li,val):
low = 0
high = len(li) -1
while li[low] <= li[high]:
mid = (low+high)//2
if li[mid] == val:
print("search success! the index is:{0}".format(mid))
return None
elif li[mid] < val :
low = mid+1
else:
high = mid -1
else:
print("val is not exist")
return None
# 二分查找递归版：
def bin_search_rec(li,val,low,high):
mid = (low+high)//2
while li[low] <= li[high]:
if li[mid] == val:
print("search success! the index is:{0}".format(mid))
return None
elif li[mid] < val:
return bin_search_rec(li, val, mid+1, high)
else:
return bin_search_rec(li, val, low, mid-1)
else:
print("val is not exist")
return None
li = [1,3,6,8,9,11,14,16,22,31,44,56,58]
bin_search_rec(li,23,0,12)
原文：http://www.cnblogs.com/hedeyong/p/7846146.html
内容总结
以上是互联网集市为您收集整理的数据结构&算法（二）_算法基础之前传（递归、时间复杂度、空间复杂度、二分查找）全部内容，希望文章能够帮你解决数据结构&算法（二）_算法基础之前传（递归、时间复杂度、空间复杂度、二分查找）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。