
课程咨询: 400-996-5531 / 投诉建议: 400-111-8989
认真做教育 专心促就业
学习算法是每一位软件编程开发程序员都必须熟练掌握的一个互联网编程开发知识点,下面我们就通过案例分析来简单了解一下,软件开发程序员算法需要掌握哪些。
复杂度分析法是对已知的代码进行效率分析的方法,与之相对的是使用实际数据运行代码的事后统计法。
复杂度分析法和事后统计法各有优劣,与复杂度分析法进行比较,事后统计法会有以下局限性:
测试结果非常依赖测试环境。硬件的不同会对测试结果有比较大的影响,比如不同处理器的执行时间会不一样
测试结果受数据的影响很大。对同一个排序算法,待排序数据的有序度会影响算法的执行时间;对于小规模的数据排序,插入排序的效率会比快速排序的效率更高
相比事后统计法,复杂度分析法更能表示一个算法在各个维度的综合性能。
复杂度
复杂度分为时间复杂度和空间复杂度,但是它们并不能准确地表示算法的执行时间和存储空间。
时间复杂度表示的是执行时间与数据规模之间的增长关系;空间复杂度表示的是存储空间与数据规模之间的增长关系。
复杂度表示法
常用的复杂度表示法就是大O复杂度表示法,时间复杂度和空间复杂度都能运用这个概念,在概念上可以进行类比。
在实际使用中,空间复杂度会比时间复杂度更简单些,下面只对时间复杂度做解析。
时间复杂度分析
变量法则
代码中的变量决定时间复杂度。
大O复杂度表示法是一种函数的表示方式,函数中存在至少一个变量,这其实就说明了大O复杂度表示法展示了代码执行时间随数据规模增长的变化趋势。
所以,在分析时间复杂度的时候,需要记住代码中的变量决定时间复杂度,观察代码中具体哪一个数据变量在实际运行中能体现运行时间的趋势。
加法法则
总复杂度等于量级大的那段代码的复杂度。
大O复杂度表示法只是表示一种变化趋势,一般认为,与公式中的高阶n值相比,常量、系数、低阶量级与算法的增长趋势关系不大。
为了降低复杂性以及提高对比性,通常会忽略掉公式中的常量、系数、低阶,只记录其中大阶的量级即可。
因此,在分析一个算法、一段代码的时间复杂度时,一般只需关注循环执行次数多的那一段代码即可。
通常,核心代码执行次数的n的量级,就是整段要分析代码的时间复杂度。
乘法法则
嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
在实际开发中,嵌套循环的代码比较常见,这里涉及到嵌套循环的时间复杂度分析。
如果把一次循环看作是n次,每次循环当中又会再做一次内循环,再把这次内循环看作是m次,这样整体循环就可以看作是n×m次,这就是乘法法则。
大部分算法复杂度分析中,会经常遇到如n2、n3这样的时间复杂度,也使用到乘法法则。
【免责声明】:本内容转载于网络,转载目的在于传递信息。文章内容为作者个人意见,本平台对文中陈述、观点保持中立,不对所包含内容的准确性、可靠性与完整性提供形式地保证。请读者仅作参考。更多内容请加danei0707学习了解。欢迎关注“达内在线”参与分销,赚更多好礼。