1

Читаю книгу про алгоритмы и структуры данных, и не совсем понимаю, что такое инвариант цикла.

Это гарантия того, что на каждой итерации цикла происходит одно и тоже?

6
  • 1
    разве в книге по алгоритмам и структурам данных не объясняется что это такое?
    – Grundy
    19 апр 2021 в 18:14
  • Да что-то не совсем понимаю, что имеется ввиду prnt.sc/11pm7r9 19 апр 2021 в 18:21
  • Это выражение истинное на каждой итерации цикла. Для примера из книги: на каждой итерации цикла, есть такой подмассив, в котором все элементы отсортированы
    – Grundy
    19 апр 2021 в 18:44
  • не совсем дубликат, но все же Что такое инвариант в ООП?
    – tym32167
    19 апр 2021 в 19:28
  • @Grundy Но на каждой итерации цикла, по идее, есть еще и неотсортированный массив. Это тоже инвариант или я ошибаюсь? 20 апр 2021 в 0:54

1 ответ 1

7

Инвариант цикла описывает состояние данных на каждом шаге. Не всё состояние - а только то, что важно с точки зрения реализуемого алгоритма.

В доказательной алгоритмистике требуется убедиться, что состояние изменяется определённым образом, приближая нас к нужному результату.

Для пошаговой сортировки (пузырьком, вставками, выбором) существенно то, что после каждого (k-го) оборота внешнего цикла мы имеем отсортированную часть из k элементов (в том числе и до выполнения алгоритма - начальное состояние, "инициализация").

Таким образом, после каждого оборота длина отсортированной части растёт, и в конце концов отсортирован весь массив.

В данном случае состояние оставшейся части массива нас не волнует.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.