2011-gre-cs-practice-book.pdf/Q35 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 23: Строка 23:
 
{{cstest-source|2011-gre-cs-practice-book.pdf|31|35}}
 
{{cstest-source|2011-gre-cs-practice-book.pdf|31|35}}
  
 +
Напишем реализацию алгоритма на C:
 +
<code-c>
 +
void sort(int* ar, int sz)
 +
{
 +
  if (sz == 2)
 +
  {
 +
    // сравнить и свапнуть если надо
 +
    return;
 +
  }
  
 +
  sort(ar, sz-1);
 +
  sort(ar+1, sz-1);
 +
  sort(ar, 2);
 +
}
 +
</code-c>
 +
 +
Заметим, что каждый вызов функции sort (за исключением случая когда sz == 2) создает еще 2 вызова той же функции sort всегда с одинаковым sz. При этом каждый вызов функции sort в конце концов приводит к вызову операции сравнения. Следовательно получаем следующую цепочку вызовов функции: f(n) - 2*f(n-1) - 4*f(n-2) - ... - 2^n-2*f(2), следовательно в итоге получается 2^n вызовов операции сравнения и правильный ответ -- <m>\Theta(2^n)</m>.
  
 
{{question-ok|}}
 
{{question-ok|}}
 +
 +
{{checkme|[[Участник:Tiniakov.ad|Tiniakov.ad]] 12:34, 21 декабря 2024 (UTC)}}

Версия 12:34, 21 декабря 2024

Задача зарезервирована: Tiniakov.ad 12:18, 21 декабря 2024 (UTC)

Вопрос: 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 вызовов операции сравнения и правильный ответ -- .Check-me-animated.gif Решено: Tiniakov.ad 12:34, 21 декабря 2024 (UTC)

Источник — «https://discopal.ispras.ru/index.php?title=2011-gre-cs-practice-book.pdf/Q35&oldid=34592»