算法充电初级
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法充电初级,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3244字,纯文字阅读大概需要5分钟。
内容图文
![算法充电初级](/upload/InfoBanner/zyjiaocheng/829/7cfd6a1e71e34c68a879f2aa4de2ba40.jpg)
算法时间复杂度
常数时间的操作:一个操作如果和数据量没有关系,每次都是固定时间内完成的操作,叫做常数操作
时间复杂度为一个算法流程中,常数操作数量的指标。常用O(读作big O)来表示。具体来说,在常数操作数量的表达式中,
只要高阶项,不要低阶项,也不要高阶项的系数,剩下的部分如果记为f(N),那么时间复杂度为O(f(N))。
例如 O( 1/100 * N2 + 100 N + 5 ) 我们也认为它的时间复杂度为 O(N2)读作big o
O (10000N) 时间复杂度为 O(N),并且指标上 O(N)> O(N2)
重点就是忽略系数和常数项
评价一个算法流程的好坏,先看时间复杂度的指标,然后再分析不同数据样本下的实际运行时间,也就是常数项时间。下面是一个插入排序算法python实现
def insert_sort(collection):
# 插入排序,大放右小放左
# 若是小放左,小继续跟前一个比较
for i in range(len(collection)-1):
while i >= 0 and collection[i+1] < collection[i]:
collection[i], collection[i+1] = collection[i+1], collection[i]
# 神来之笔,把交换后的小的那个数再与前面比
# 值得注意的是,python的for不是通过++来下移,而是赋值!
i -= 1
return collection
这个插入排序假如要排序的序列一开始就是有序的,只要执行一遍for,也就是O(n)。最坏情况是逆序,此时时间复杂度就是O(n²)。所以此时时间复杂度取决于输入的数据,此时如何评价呢,一律用最差情况来估计时间复杂度!
# 归并排序 用到了递归
def merge_sort(collection):
# 先采用递归对把数组对半排列好
# 然后使用外排算法合并成一个有序数组
length = len(collection)
if length == 1:
return collection
mid = length // 2
left_part = merge_sort(collection[:mid])
right_part = merge_sort(collection[mid:])
i = 0
j = 0
k = 0
left_length = len(left_part)
right_length = len(right_part)
while i < left_length and j < right_length:
if left_part[i] < right_part[j] :
collection[k] = left_part[i]
i += 1
else:
collection[k] = right_part[j]
j += 1
k += 1
while i < left_length:
collection[k] = left_part[i]
i += 1
k += 1
while j < right_length:
collection[k] = right_part[j]
j += 1
k += 1
return collection
对于用到递归的时间复杂度都满足式子 T(N) = a*T(N/b) + O(N^d) ,比如上面的归并排序,T(N) = 2 * T(N/2) + O(N) ,第一部分是因为递归把数据各分分一半去排序,所以是 2 * T(N/2),第二部分外排最坏情况是N,所以是O(N)。那么这种式子如何计算时间复杂度,利用到了以下的式子。
T(N) = a*T(N/b) + O(Nd)
1) log(b,a) > d -> 复杂度为O(N^log(b,a))
2) log(b,a) = d -> 复杂度为O(N^d * logN)
3) log(b,a) < d -> 复杂度为O(N^d)
归并排序比冒泡和选择排序快的原因在于,选择和冒泡排序确定一个数的位置需要从头遍历一遍 ,其中进行了太多无效的比较,所以造成了时间的浪费。而归并排序快的原因,在于更好的利用了每次排序的信息,例如merge中两个有序数组的合并利用了外排。归并排序适合解决以下问题。
第一题代码答案,其实质是把数据[1,3,4,2,5]不断二分,最终分得左边两个数1,3的时候,很容易算出小和1,算完了小和之后就要对这一部分排序,即对这两个数排序(已经算了小和,排序对结果没有影响),当左边与右边比较的时候也是同样的道理,比如[1,4],与右边[ 2,5 ],利用外排的思想,首先lp指向1,rp指向2,比较可知2大于1,所以rp剩下所有部分都比1大会产生rl-j个1小和。基本就是这个思想,某个数产生的小和其实就是这个数乘以右边比它大的所有数的积。
while i < ll and j < rl:
if lp[i] < rp[j]:
answer += lp[i] * (rl - j) # 只是多了这一句
collection[k] = lp[i]
i += 1
else:
collection[k] = rp[j]
j += 1
k += 1
对数器
写完一道算法题,如何验证是否正确。首先要有随机数据生成器,第二是绝对正确的算法(时间复杂度可以差,但是绝对正确,也可以是内置函数等),最后就是大样本测试。(排序,堆都可以准备一个对数器再上场面试)
内容总结
以上是互联网集市为您收集整理的算法充电初级全部内容,希望文章能够帮你解决算法充电初级所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。