当比较花费任何时间

我要排序的阵列，A，根据本成本模式排序：当比较花费任何时间

对于任何x值，形式A的分配[I] = x具有的成本1.另外，A [i] = A [j]的成本为1.
其他操作，如比较和分配for x = A [i]（其中x不是阵列）的成本为0.

问题：

给一个下界排序的阵列A.你的答案应该是在正方面的精确表达式，而不是使用渐近记法所要求的最坏情况下的时间。
描述使用O（n）空间的排序算法。运行时应该与1中给出的下界完全匹配（确切地说，不是渐近地）。
描述对这个成本模型最优的就地排序算法。运行时应该完全匹配1中给出的边界（完全不是渐近地）。

我尝试：

ñ。这是因为，在最糟糕的情况下，数组中的n个元素处于索引中，因此它们将不需要处理。因此，需要n个赋值才能按排序顺序获取数组。

我的算法psudo代码：

def weird_sort(A): 
    B = an array the same size of A 
    C = an array of bools (default True) the same size of A 
    for i in range(0, A.size): 
     min = first index in c that is True 
     for j in range(0, A.size): 
      if (A[j] < A[min]) and (C[j]): 
       min = j 
     B[i] = A[min] 
     C[i] = False 
    A = B

我认为这恰恰是N次跑，因为我们正在进入一个指定任何唯一的一次是在最后一行，在那里我们复制B的内容变成A.

不知道从哪里开始。在我看来，为了保持一切到位，我们必须交换数组A中的东西，但是我无法弄清楚如何去掉如何用n/2交换对数组进行排序。有人能让我朝着正确的方向前进吗？你也可以仔细检查我的答案1和2吗？

来源

2017-10-22 Jean Hans

这可能是一个更好的问题https://cs.stackexchange.com/ – Stedy

这听起来像循环排序发明的确切情况。 :-) – templatetypedef

我认为就地允许O(1)额外变量，因为否则我不认为这是可能的

首先让解决子问题：鉴于i，发现这应该是上个i位置的数字。因为比较是免费的，所以可以使用bruteforce。

现在复制第一个元素（到附加变量），找到最小的元素并将其放在位置1.现在这个元素位于i的位置。让我们找到应该在位置i上的元素并将其复制到此处（假设它位于位置j），现在找到属于位置j等的元素。最后，我们找到了我们最初复制的元素，将其放回。因此，我们使用k赋值（在循环结构中）将k变量设置为它们的位置。现在对所有其他元素都做同样的事情。你无法记住每个变量是否放在原处，但是你可以检查它是否在它的位置上是免费的。

如果有一本相等的元素应该慎重些，但尽管谈论高效排序算法时，它仍然应该工作

来源

2017-10-22 01:59:39 RiaD

，我们通常会倾向于对快速排序讲，这种算法进行了优化比较次数。

但是，其他算法尝试优化内存访问的次数（与您的情况一样）。其中一些被称为缓存遗忘算法（不对特定内存层次结构参数进行假设）和缓存感知（针对特定内存层次结构进行调整）。你可以找到这种算法，所以你可能有兴趣给他们看看。

作为一个例子，Harald Prokop's PhD thesis讨论了缓存遗忘算法，并提出了分配排序，它将子组中的数据部分排序，这些子组可能适合存储器层次结构的较低分区。

分布排序使用O(n ln(n))工作，并会导致O(1+ (L/n)*(1+logz(n))高速缓存未命中ň元素进行排序。

其中大号是一个高速缓存银行的规模和ž缓存本身的大小。性能模型只假定只有一个高速缓存级别，但由于不知情的属性而适应所有高速缓存级别。

其基本概念是分配成本根据元素放置在内存层次结构中的位置而变化。

来源

2017-10-23 08:21:44

当比较花费任何时间

回答

相关问题