эффективный способ проверить, есть ли в массиве все целые числа от 0 до n-1

Question

относительно моего предыдущего поста: Сложность, чтобы найти, если в массиве отсутствует элемент -> Я пытаюсь решить алгоритм, чтобы проверить, есть ли в массиве все элементы от 0 до n - 1 наиболее эффективным способом (с учетом сложности времени) без дополнительного массива. я придумал два решения. Не могли бы вы помочь мне определить, какой из них более эффективен? в какой я должен сдаться? благодарю вас.

/* first attempt */

int check_missing_a(int *a, int n)
{
    int i, flag = 0;

    for (i = 0; i < n; i++)
    {
        if (a[i] < 0 || a[i] >= n) //check for unwanted integers
            return 0;

        while (i != a[i])
        {
            swap(&a[a[i]], &a[i]); //puts numbers in their index

            flag++;
            if (flag > 1 && a[i] == a[a[i]]) //check for duplicates
                return 0;
        }
        flag = 0;
    }

    return 1;
}


/* second attempt */

int check_missing_b(int *a, int n)
{
    int i, sum_a = 0, sum_i = 0, sum_aa = 0, sum_ii = 0;

    for (i = 0; i < n; i++)
    {
        if (a[i] < 0 || a[i] >= n) //check for unwanted integers
            return 0;

        else
        {
            sum_a += a[i]; // sum of 'elements' should be equal to sum of 'i' 
            sum_i += i;

            sum_aa += a[i] * a[i]; // multiplication sum of 'elements' should be equal to multiplication sum of 'i' 
            sum_ii += i * i;
        }
    }
    return (sum_aa == sum_ii && sum_a == sum_i);
}

Answer 1

Прежде всего, нам нужно исправить check_missing_a, потому что он глючит. После обмена a[i] может выйти за пределы для следующего a[a[i]]. Исправленная версия:

int check_missing_a2(int *a, int n) {
    for (int i = 0; i < n; ++i) {
        while (i != a[i]) {
            if (a[i] < i || a[i] >= n || a[i] == a[a[i]])
                return 0;

            swap(&a[i], &a[a[i]]);
        }
    }

    return 1;
}

Мы даже можем сохранить несколько сравнений следующим образом: (Спасибо @chmike)

int check_missing_a2(int *a, int n)
{
    for (int i = 0; i < n; ++i)
        if (a[i] < 0 || a[i] >= n)
            return 0;

    for (int i = 0; i < n; ++i) {
        while (i != a[i]) {
            if (a[i] == a[a[i]])
                return 0;

            swap(&a[i], &a[a[i]]);
        }
    }

    return 1;
}

---

Сложность check_missing_a2

На первый взгляд можно подумать, что check_missing_a2 медленнее, чем O (N), потому что внешний l oop делает N проходов, и есть еще один внутренний l oop.

Однако внутренний l oop выполняет не более N-1 перестановок. Например, следующее иллюстрирует количество свопов для каждого расположения чисел в 0..N-1 для N = 8:

# swaps   # arrangements
-------   --------------
      0                1
      1               28
      2              322
      3             1960
      4             6769
      5            13132
      6            13068
      7             5040

Как объясняется @ 4386427, каждый своп размещает по крайней мере один элемент в его правильная позиция. Следовательно, не может быть больше N перестановок.

Это означает, что ни одна часть функции не будет выполнена более 2 * N раз, что приведет к сложности O (N).

---

Сложность check_missing_b

Один l oop с N проходами для сложности O (N).

---

Что касается фактическая производительность, я подозреваю, что check_missing_a2 всегда будет быстрее, чем check_missing_b.

Конечно, есть также проблема, что check_missing_a2 меняет массив и что check_missing_b может переполниться.

Answer 2

Функция check_missing_b определенно является O (n), потому что она имеет только один l oop. Он также имеет свойство не изменять входной массив a. Тем не менее, он имеет ограничение по величине n, поскольку sum_ii может переполниться.

Функция check_missing_a имеет два цикла и менее очевидна для анализа. Он также сортирует значения в массиве a и таким образом модифицирует входной массив. Это может быть проблемой. С другой стороны, она не подвержена переполнению, что является преимуществом по сравнению с другой функцией.

Эта функция является радикальной сортировкой, поскольку каждый своп помещает значение в свое окончательное место. Будет меньше чем n свопов. Таким образом, эта функция имеет вид O (n).

К сожалению, эта функция также имеет проблему. Значение a[a[i]] может быть больше, чем n, когда a[i] > i. Функция требует, таким образом, двух проходов по элементам. Первый проход гарантирует, что никакое значение не будет меньше 0 и больше, чем n-1. Второй проход делает радикальную сортировку.

Вот моя предложенная реализация функции check_missing_a.

int check_missing_c(int *a, int n)
{
    for (int i = 0; i < n; i++)
        if (a[i] < 0 || a[i] >= n)
            return 0;
    for (int i = 0; i < n; i++)
        while (i != a[i]) {
            if (a[i] == a[a[i]])
                return 0;
            int tmp = a[i];
            a[i] = a[tmp];
            a[tmp] = tmp;
        }
    return 1;
}