Radix Sort является примером сложности алгоритма P или NP? - PullRequest
0 голосов
/ 15 июня 2019

Проблема упорядочения вектора по 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);
}

1 Ответ

1 голос
/ 15 июня 2019

Конечно, это в P! так как его сложность полиномиальна. Ответ на остальные вопросы связан с отношением этих классов сложностей. П находится в НП. Следовательно, радикальная сортировка находится в NP. Поскольку мы не знаем какого-либо полиномиального агорифма для задач NP-Complete, следовательно, мы не знаем, находится ли он в NP-Complete или нет, и это связано с известной проблемой P = NP?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...