Powershell 排序函数时间复杂度

Question

我无法在 Sort-Object cmdlet 的 Microsoft 文档中找到此信息。

我正在使用 Powershell 的 Sort-Object 根据属性对对象进行排序，即：Azure RunBook 中的 $foo | Sort-Object -Property x，这个的时间复杂度是多少？

Answer 1

我想你可以自己看看，只需更改 $elements 对象上的值即可。我认为这是linear time O(n)但是我不是这方面的专家。

$elements = [pscustomobject]@{
    Minimum = 100
    Maximum = 2000
    Incremental = 100
}

$testRuns = 49

for($i=$elements.minimum;$i -le $elements.maximum;$i=$i+$elements.incremental)
{
    $arr = 0..$i | ForEach-Object {
        [pscustomobject]@{
            Value = Get-Random -Maximum 1000
        }
    }

    0..$testRuns | ForEach-Object {
        Measure-Command { $arr | Sort-Object Value }
    } |
    Measure-Object TotalMilliseconds -Maximum -Average -Minimum |
    Select-Object @{n='Elements';e={$i}},Average,Maximum,Minimum
}

输出

Elements   Average Maximum Minimum
--------   ------- ------- -------
     100  0.698054  7.8588  0.3769
     200  0.893544  1.9095  0.7365
     300   1.43093  2.4781  1.1179
     400  2.052776  3.7096  1.5384
     500  2.381598  3.5417  1.9008
     600  3.277292  4.9029  2.3808
     700   3.37905  6.2258  2.6886
     800  4.177368  6.4848  3.0926
     900  4.626102  5.8873  3.5225
    1000   4.94238  6.9827  3.8871
    1100  6.062798 25.2185  4.4134
    1200  6.649458  8.4747  5.4431
    1300  7.304344 10.1546  5.9863
    1400   8.16644  11.657  6.5452
    1500  8.179668 11.9478  6.1667
    1600   9.44597 13.1438  7.0721
    1700  9.983092 12.9889  7.4455
    1800 11.246036 15.7499   8.538
    1900 11.000806 15.5332  8.3169
    2000 13.556442 24.1767  8.7538

Answer 2

在GitHub, Sort-Object uses List<T>.Sort() to sort the objects. And according to this SO anwser上可以看出，它的时间复杂度是O(n log n)。

Powershell 排序函数时间复杂度

Powershell Sort Function Time Complexity

powershell

azure-powershell

azure-runbook

输出