2011-gre-cs-practice-book.pdf/Q35

Вопрос: Q35-08c765

Рассмотрим следующий алгоритм, сортирующий массив из n ≥ 2 целых чисел:

1. Если в массиве всего 2 элемента, сравнить их и поменять местами если они в неправильном порядке
2. Иначе, делать следующие шаги по порядку:
   1. Рекурсивно отсортировать первые n-1 элементов массива
   2. Рекурсивно отсортировать последние n-1 элементов массива
   3. Рекурсивно отсортировать первые 2 элемента массива

Какова асимптотическая временная сложность этого алгоритма, измеряемая количеством проведенных сравнений?

Ответы

• Правильный ответ:

Объяснение

Исходники — вопрос 35 на 31 странице книги «2011-gre-cs-practice-book.pdf»

Напишем реализацию алгоритма на C:

void sort(int* ar, int sz)
{
  if (sz == 2)
  {
    // сравнить и свапнуть если надо
    return;
  }
 
  sort(ar, sz-1);
  sort(ar+1, sz-1);
  sort(ar, 2);
}

Заметим, что каждый вызов функции sort (за исключением случая когда sz == 2) создает еще 2 вызова той же функции sort всегда с одинаковым sz. При этом каждый вызов функции sort в конце концов приводит к вызову операции сравнения. Следовательно получаем следующую цепочку вызовов функции: f(n) - 2*f(n-1) - 4*f(n-2) - ... - 2^n-2*f(2), следовательно в итоге получается 2^n вызовов операции сравнения и правильный ответ -- .

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.