algorithm - Radix Sort 是复杂算法 P 还是 NP 的一个例子？

Question

用 Radix Sort 排序向量的问题是复杂度算法 P 的一个例子？

我不知道它是 NP-Complete 还是 NP。

void radixsort(int vector[], int size) {
    int i;
    int *b;
    int bigger= vector[0];
    int exp = 1;

    b = (int *)calloc(size, sizeof(int));

    for (i = 0; i < size; i++) {
        if (vetor[i] > bigger)
            size= vector[i];
    }

    while (bigger/exp > 0) {
        int bucket[10] = { 0 };
        for (i = 0; i < size; i++)
            bucket[(vetor[i] / exp) % 10]++;
        for (i = 1; i < 10; i++)
            bucket[i] += bucket[i - 1];
        for (i = size- 1; i >= 0; i--)
            b[--bucket[(vector[i] / exp) % 10]] = vector[i];
        for (i = 0; i < size; i++)
            vector[i] = b[i];
        exp *= 10;
    }

    free(b);
}

Answer 1

当然是在P啦!因为它的复杂性是多项式的。回答其他问题与这些复杂性类别的关系有关。 P 在 NP 中。因此，基数排序属于 NP。由于我们不知道 NP-Complete 问题的任何多项式算法，因此我们不知道它是否在 NP-Complete 中，它与已知问题 P = NP 有关吗？