algorithm - 如何计算这个基数排序算法的复杂度？

Question

我有以下代码。我需要计算这个算法的复杂度，但我不知道从哪里开始。这个算法有 3 个嵌套循环，所以我猜它的复杂度是 n^3 还是我错了？

public static void RadixSort(DataArray 数据) { IList> digits = new List>();

        for (int i = 0; i < 10; i++)
        {
            digits.Add(new List<int>());
        }

        for (int i = 0; i < data.Length; i++)
        {
            for (int j = 0; j < data.Length; j++)
            {
                int digit = (int)((data[j] % Math.Pow(10, i + 1)) / Math.Pow(10, i));

                digits[digit].Add((int)data[j]);
            }

            int index = 0;
            for (int k = 0; k < digits.Count; k++)
            {
                IList<int> selDigit = digits[k];

                for (int l = 0; l < selDigit.Count; l++)
                {
                    data.Swap(index++, selDigit[l]);
                    //data[index++] = selDigit[l];
                }
            }

            for (int k = 0; k < digits.Count; k++)
            {
                digits[k].Clear();
            }
        }
    }

Answer 1

计算复杂度比只看嵌套循环的数量要复杂得多。如果你有一个像这样的三重嵌套循环:

for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
        for(int k=0; k<n; k++)

它将是 O(n³)，假设 n 在循环中没有变化。但是，如果您考虑您的情况:

for(int i=0; i<n; i++)
    for(int j=0; j<m; j++)
        for(int k=0; k<m; k++)

时间复杂度将变为 O(m²n)。

即使是最简单的排序算法，如双向排序、选择排序和插入排序，也是复杂度为 O(n²) 的算法，因此如果您的实现比这更糟，那您就是做错了什么。基数排序的时间复杂度为 O(wn)，其中 w 是元素大小的度量。