randperm基于什么算法? [英] What algorithm is randperm based on?

问题描述

在哪里可以找到Matlab的randperm函数使用什么算法?是Fisher-yates(Knuth)改组算法还是其他?

Where can I find what algorithm Matlab's randperm function uses? Is it Fisher-yates (Knuth) shuffling algorithm or something else?

推荐答案

对于早于R2009b的MATLAB版本，randperm的实现方式如下:

For MATLAB releases as early as R2009b, randperm is implemented as follows:

function p = randperm(n)
    [ignore, p] = sort(rand(1, n));

您可以通过键入以下内容自己查看:

You can see it for yourself by typing:

type randperm

基本上randperm会生成 n 个数字并将其排序，然后将所得的有序索引p数组作为随机排列返回.这样做的时间复杂度充其量是 O ( n log n )，比

Basically randperm generates n numbers and sorts them, returning the resulting array of ordered indices p as the random permutation. The time complexity for this is O(nlogn) at best, worse than Fisher-and-Yates' shuffle, which runs at O(n).

编辑:Dennis指出，在更高版本中，randperm在 O ( n )时间运行，因此显然它得到了改进.但是，它是一个内置函数，因此无法看到其实现.

Dennis points out that in later releases randperm runs at O(n) time, so obviously it's improved. However, it's a built-in function so it is impossible to see its implementation.

这篇关于randperm基于什么算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！