Блог

Главная - Вопросы по программированию - Сложность Вставки в молодую таблицу

Сложность Вставки в молодую таблицу

#arrays #sorting #matrix #time-complexity

Вопрос:

Подумайте, что у меня есть такая юная картина, как эта ->

 10 11 12 15
16 18 20 22
25 27 30 34
35 40 44 Infinity

Бесконечность обозначает пустой элемент

  • У меня есть алгоритм, в котором я помещаю элемент в правом нижнем углу, затем сдвигаю его как можно выше, а затем как можно левее.
  • Я вставляю 8.
 10 11 12 15
16 18 20 22
25 27 30 34
35 40 44 8
  • Переместите его как можно выше, а затем как можно левее. 15,22,34 смещены.
  8 10 11 12
16 18 20 15
25 27 30 22
35 40 44 34
  • Теперь, вернувшись после рекурсивного вызова, я помещаю 15 в нужное место. 22 в правильном месте. Затем 34 в правильном месте.
  8 10 11 12
15 16 18 20
22 25 27 30
34 35 40 44

По моему мнению , временная сложность всей операции равна O(m*n), где m, n-размеры матрицы.
Алгоритм

  1. Поместите элемент в правый нижний угол.
  2. Переместите его как можно выше.
  3. Затем переместите его как можно левее.
  4. После завершения рекурсивного вызова поместите перемещенные элементы в нужное место.

Правильно ли я определил временную сложность? O(m*n)

Комментарии:

1. Я не понимаю, где находится рекурсивная часть, но перемещение одного элемента на его место, на мой взгляд, равно O(m n), а затем вы делаете это k раз.

2. Что такое k здесь?

Метки: