时间:2021-05-02
介绍
排序是将一组数据,依指定的顺序进行排列的过程
内部排序:指将需要处理的所有数据都加载到内部存储器中进行排序.常见的内部排序有:直接插入排序、希尔排序、简单选择排序、堆排序、冒泡排序、快速排序、归并排序、基数排序。
外部排序:数据量过大,无法全部加载到内存中,需要借助外部存储进行排序。
度量一个程序(算法)执行时间的两种方法:
事后统计方法这种方法可行,但是有两个问题:一是要想对设计的算法的运行性能进行评测,需要实际运行该程序;二是所得时间的统计量依赖于计算机的硬件\软件等环境因素,这种方式,要在同一台计算机的相同状态下运行,才能比较哪个算法速度更快.
事前估计方法通过分析算法的时间复杂度来判断哪个算法更优.
一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行的次数多,它花费时间就多.一个算法中语句执行次数称为语句频度或时间频度.记为T(n).
比如计算1-100所有数字之和,有两种算法
执行次数取决于end长度.它的T(n)=n+1.
直接计算只需执行一次即可,它的T(n) = 1.
估算时间频度时注意事项:
无论代码执行了多少行,只要是没有循环等复杂结构,那这个代码的复杂度就是O(1)
上述代码在执行的时候,它消耗的时间并不是随着某个变量的增长而增长,那么无论这类代码有多长,即使有几万几十万行,都可以用O(1)来表示它的时间复杂度.
在while循环里面,每次都将i乘以2,乘完之后,i距离n就越来越近了.假设循环x次之后,i就大于n了,此时循环就结束了,也就是说2的x次方等于n,那么x= log2n也就是说当循环log2n次以后,这个代码就结束了.因此这个时间复杂度为O(log2n).
for循环里面的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以使用O(n)来表示它的时间复杂度.
这个线性对数阶O(log2n)就是将时间复杂度为O(logn)的代码循环N遍.
即双层for循环,n*m
3层循环
k次循环
常见的算法时间复杂度由小到大依次为:O(1)
原文地址:https://www.toutiao.com/i6939136887474962983/
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了java数据结构与算法之冒泡排序。分享给大家供大家参考,具体如下:前面文章讲述的排序算法都是基于插入类的排序,这篇文章开始介绍交换类的排序算法,即
前言:Java数据结构与算法专题会不定时更新,欢迎各位读者监督。本文从最简单的一个排序算法——桶排序开始,分析桶排序的实现思路,代码实现
排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容
本文实例讲述了java数据结构与算法之简单选择排序。分享给大家供大家参考,具体如下:在前面的文章中已经讲述了交换类的排序算法,这节中开始说说选择类的排序算法了,
HashMap排序是数据结构与算法中常见的一种排序算法。本文即以Android平台为例来实现该算法。具体代码如下:publicstaticvoidmain(St