相关疑难解决方法(0)

我很好奇为什么如果我们使用链接列表实现的存储桶,则存储桶排序的运行时间为O(n + k).例如,假设我们有这个输入:

n = no of element= 8
k = range = 3

array = 2,2,1,1,1,3,1,3

桶将如下所示:

1: 1 -> 1 -> 1 -> 1
2: 2 -> 2
3: 3 -> 3

插入这些桶的总时间是O(n),假设我们在链表中存储尾指针.

要删除,我们必须转到每个存储桶,然后删除该存储桶中的每个节点.因此,当我们遍历每个链表时,复杂性应该是O(K*桶的链接列表的平均长度).

但是,我读到了bucket sort的复杂性是O(n + k).为什么这不符合我的分析？请更正我,因为我仍在学习计算复杂性.

我想探讨一下我对桶排序的分析，如下所示。
\n桶排序的实现方式有很多种。其中一些如下。
\n类型 1:
\nif\xc2\xa0we\xc2\xa0know\xc2\xa0the\xc2\xa0range\xc2\xa0of\xc2\xa0our\xc2\xa0elements\xc2\xa0to\xc2\xa0be\xc2\xa0sorted,\xc2 \xa0we\xc2\xa0can\xc2\xa0set\xc2\xa0up\nbuckets\xc2\xa0for\xc2\xa0each\xc2\xa0possible\xc2\xa0element,\xc2\xa0and\xc2\xa0just\xc2\xa0toss\xc2\xa0elements\ xc2\xa0进入\xc2\xa0其\xc2\xa0对应的\xc2\xa0buckets。\xc2\xa0我们\xc2\xa0然后\n清空\xc2\xa0的\xc2\xa0buckets\xc2\xa0in\xc2\xa0order,\xc2\xa0and\xc2\ xa0the\xc2\xa0result\xc2\xa0is\xc2\xa0a\xc2\xa0sorted\xc2\xa0list.\n在\xc2\xa0实现\xc2\xa0这个\xc2\xa0算法，\xc2\xa0we\xc2\xa0can\xc2\xa0easily\ xc2\xa0use\xc2\xa0an\xc2\xa0array\xc2\xa0to\xc2\xa0代表\xc2\xa0our\xc2\xa0buckets,\xc2\xa0where\xc2\xa0the\xc2\xa0value\xc2\xa0at\neach\xc2\xa0array \xc2\xa0index\xc2\xa0将\xc2\xa0表示\xc2\xa0\xc2\xa0的编号\xc2\xa0的\xc2\xa0elements\xc2\xa0in\xc2\xa0\xc2\xa0对应的\xc2\xa0桶。\xc2\xa0If\ xc2\xa0we\xc2\xa0have\xc2\xa0integers\non\xc2\xa0the\xc2\xa0range [0..max],\xc2\xa0then\xc2\xa0we\xc2\xa0set\xc2\xa0up\xc2\xa0an\xc2 \xa0array\xc2\xa0of\xc2\xa0(max + 1)\xc2\xa0integers\xc2\xa0and\xc2\xa0初始化\xc2\xa0all\xc2\xa0the\xc2\xa0values\xc2\xa0to\nzero。\xc2\xa0We \xc2\xa0然后\xc2\xa0继续\xc2\xa0顺序\xc2\xa0到\xc2\xa0the\xc2\xa0unsorted\xc2\xa0array,\xc2\xa0reading\xc2\xa0the\xc2\xa0value\xc2\xa0of\xc2\xa0each\ xc2\xa0element,\xc2\xa0going\n到\xc2\xa0的\xc2\xa0对应的\xc2\xa0index\xc2\xa0in\xc2\xa0the\xc2\xa0buckets\xc2\xa0array,\xc2\xa0和\xc2\xa0递增\xc2\ xa0\xc2\xa0值\xc2\xa0那里。

时间：O(N)
\n空间：O(1)
\n类型2：

示例：按年龄对人员数组进行排序
\n年龄与用于排序的任意整数有些不同。因此它的范围很小[0-150]（所有人的年龄都在0到150之间）。因此，最快的排序方法是分配 151 个链表（我们称之为桶），并根据每个人的年龄将每个人的数据结构放入桶中：

时间：O(N+K)
\n空间：O(N+K)\n

类型 3（维基百科中所示的类型 2 的变体）

函数nextSort是一个排序函数，用于对每个桶进行排序。如果使用插入排序，那么最坏的时间复杂度为 O(n^2)，或者使用合并排序，这样我就可以保持 O(nlgn) 的稳定性。

\n
• 问题：
  \n1>如何被认为是线性排序，是因为类型1还是类型2？
  \n2>如果我像WIkepedia一样使用Type 3，哪种排序可以有效地对每个桶进行排序？
  \n我知道在实践中使用插入排序的原因是我们期望桶很小，对于小列表，插入排序比其他任何方法都快得多。即使在实现合并排序或快速排序时，当列表变得足够小时（例如低于 20 个项目左右），也会使用插入排序。
  \n3>对于类型 3，我可以根据什么来决定存储桶的范围？
  \n这很重要，因为如果您尝试使用大量存储桶（例如远大于 n）进行存储桶排序，则运行时可能主要取决于扫描所有存储桶以查找您实际使用的存储桶所需的时间，即使其中大部分都是空的。
\n

我根据以下内容进行了分析：
\n维基百科
\n桶排序的复杂度怎么可能是 O(n+k)？
\n算法的设计与分析\n1996 年 1 月 23 日讲义
\n http://www1bpt.bridgeport.edu/~dichter/lilly/bucketsort.htm
\n http://cs.nyu.edu/courses/fall02 /V22.0310-002/lectures/lecture-23.html
\n如果我们使用链表实现桶，那么桶排序的复杂度是 …