gpt4 book ai didi

arrays - 什么时候值得对数组进行排序?

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:34:34 25 4
gpt4 key购买 nike

<分区>

多年前,在一次求职面试中,有人问我:什么时候值得对数组进行排序?我记得没能正确回答,最近我做了一个算法类(class),我得出的结论是提供一个更“学术”的回答可能会让我得到那份工作......无论如何,不​​可能修复过去, 到目前为止,我正在尝试正式地回答自己,目前,这就是我所在的位置:

给定一个数组,搜索的时间为

  • 如果没有排序则为O(n)
  • O(log(n)) 如果排序

考虑到快速排序在 O(n*log(n)) 中排序

什么时候值得对数组进行排序?这当然取决于我们要搜索数组的次数。

  • 在排序数组中搜索 x 次的成本 = O(n*log(n)) + [O(log(n)) * x]
  • 在未排序数组中搜索 x 次的成本 = O(n) * x

x 的值是多少?

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com