|簡體中文

比思論壇

 找回密碼
 按這成為會員
搜索



查看: 544|回復: 1
打印 上一主題 下一主題

为什么说算法是程序猿“修仙”的必经之地?

[複製鏈接]

1053

主題

45

好友

6157

積分

教授

Rank: 8Rank: 8

  • TA的每日心情

    昨天 10:43
  • 簽到天數: 2509 天

    [LV.Master]伴壇終老

    推廣值
    0
    貢獻值
    1205
    金錢
    4774
    威望
    6157
    主題
    1053

    回文勇士 文明人 中學生 高中生 文章勇士 附件高人 簽到勳章 簽到達人 附件達人

    樓主
    發表於 2019-1-1 13:18:22
    1.算法主要衡量标准
    1、时间复杂度(运行时间)
    在算法时间复杂度维度,我们主要对比较和交换的次数做对比,其他不交换元素的算法,主要会以访问数组的次数的维度做对比。
    其实有很多同学对于算法的时间复杂度有点模糊,分不清什么所谓的 O(n),O(nlogn),O(logn)等,也许下图对一些人有一些更直观的认识。

    2、空间复杂度(额外的内存使用)
    排序算法的额外内存开销和运行时间同等重要。就算一个算法时间复杂度比较优秀,空间复杂度非常差,使用的额外内存非常大,笔者认为它也算不上一个优秀的算法。
    3、结果的正确性
    这个指标是笔者自己加上的,我始终认为一个优秀的算法最终得到的结果必须是正确的。就算一个算法拥有非常优秀的时间和空间复杂度,但是结果不正确,又有什么意义呢?

    2.原理
    每次在无序的列表中取一个元素插入到一个有序列表的适当位置,成为一个元素加1的新的有序列表。
    插入排序根据原理又分为直接插入排序、二分插入排序、希尔排序等,今天主要讲一下直接插入排序。直接插入排序是一种稳定的排序算法。
    假设排序顺序从左至右,具体步骤如下:
    1、列表第一个元素和前面元素比较,如果小于前面元素(其实不存在),则交换位置(这步其实可以没有)。
    2、列表第二个元素和前面元素(第一个元素)比较,如果小于前面元素,则交换位置。
    3、列表第三个元素和前面元素(第二个元素)比较,如果小于前面元素,则交换位置。如果和前面元素交换了位置,现在在第二个位置上,则接着继续和前面元素比较(第一个元素),如果小于前面元素,接着再次交换位置,然后再次重复比较过程......
    4、继续重复以上过程,直到最后一个元素完成比较。
    比较移动过程中,如果元素不需要移动意味着该元素排序完毕。
    网络上的插入排序大多都是新建一个有序列表用来存放最终结果,其实在无序列表上进行排序操作空间复杂度才更优。
    也许一张更直观的图比上千句话效果都好。

    3.复杂度
    1、时间复杂度
    比较次数
    对于长度为N的主键不重复的列表,插入排序平均情况下需要n²/4次比较,最坏情况下需要n²/2次比较,最好的情况下需要n-1 次比较。
    交换次数
    对于长度为N的主键不重复的列表,插入排序平均情况下需要n²/4次交换,最坏情况下需要n²/2次交换,最好情况下需要0次交换。
    4.性能和特点
    总体来说,直接插入排序是一种比较简单的排序算法,很容易理解也很好用代码实现,当然它的特点也很明显:运行时间和数据初始状态有关。
    插入排序的思想是把一个元素插入一个有序的列表中,假如这个元素的位置正好是有序部分的末尾呢?也就是说当前元素不用移动位置。
    再一次假如整个列表都是有序的会发生什么情况呢?根本就不需要移动任何元素。这也就是为什么在最好的情况下交换次数为0,比较次数为n-1的原因。
    假如列表的很大一部分元素是有序的,插入排序可能比大多数排序算法都要快。
    5.适用场景
    直接插入排序对于小型列表或者非随机元素列表很有效。例如:部分元素有序。大体可归纳为:
    1、每个元素距离自己的最终位置都不远;
    2、一个有序的大列表连接一个小列表;
    3、列表中只有少数元素不正确。
    6.其他
    为什么插入排序是稳定呢?
    插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。
    比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。
    如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。
    所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

    292

    主題

    0

    好友

    1503

    積分

    大學生

    Rank: 6Rank: 6

  • TA的每日心情
    無聊
    2021-4-21 09:05
  • 簽到天數: 284 天

    [LV.8]以壇為家I

    推廣值
    0
    貢獻值
    68
    金錢
    1013
    威望
    1503
    主題
    292

    回文勇士 文章勇士 文明人 中學生 高中生 簽到勳章 簽到達人 大學生

    沙發
    發表於 2019-1-9 10:13:23
    分享辛苦了,回帖是我的支持~1
    这一秒不失望,下一秒就有希望~!
    重要聲明:本論壇是以即時上載留言的方式運作,比思論壇對所有留言的真實性、完整性及立場等,不負任何法律責任。而一切留言之言論只代表留言者個人意見,並非本網站之立場,讀者及用戶不應信賴內容,並應自行判斷內容之真實性。於有關情形下,讀者及用戶應尋求專業意見(如涉及醫療、法律或投資等問題)。 由於本論壇受到「即時上載留言」運作方式所規限,故不能完全監察所有留言,若讀者及用戶發現有留言出現問題,請聯絡我們比思論壇有權刪除任何留言及拒絕任何人士上載留言 (刪除前或不會作事先警告及通知 ),同時亦有不刪除留言的權利,如有任何爭議,管理員擁有最終的詮釋權。用戶切勿撰寫粗言穢語、誹謗、渲染色情暴力或人身攻擊的言論,敬請自律。本網站保留一切法律權利。

    手機版| 廣告聯繫

    GMT+8, 2024-11-1 07:30 , Processed in 0.026603 second(s), 29 queries , Gzip On.

    Powered by Discuz! X2.5

    © 2001-2012 Comsenz Inc.

    回頂部