Вопрос о "времени работы" цикла for

Question

Я начал читать книгу «Введение в алгоритмы, третье издание», и я столкнулся с тем, что мне не совсем понятно, по поводу алгоритма «вставка-сортировка».

Пожалуйста, посмотрите на пи c сначала:

Прежде всего, автор определил n = A.length . A.length - это длина массива A.

Итак, предположим, что длина массива "A" равна 5. Если я запускаю для l oop от j = 2 (как на рисунке) до A.Length = 5, я бы сказал, что первая строка будет работать 4 раза, то есть n - 1 раз для любого n. С другой стороны, автор пишет, что первая строка будет выполняться n раз.

Что мне не хватает?

Answer 1

Первая строка, вероятно, относится к числу проверок условия. Если ваш l oop выполняется n-1 раз, условие итератора проверяется n раз (в том числе в конце, когда оно становится ложным). Внутри тела l oop все операторы были отмечены n-1, как и ожидалось.

Answer 2

Это n может express сложность времени -> O (n ^ 2) внешнего для -l oop сортировки вставок, а не фактического l oop -счета.