MaxLich: потому что один и тот же алгоритм может иметь разные асимптотики в зависимости от входных данных. А О-большое для каждого такого варианта и обозначает худший случай
Грубо говоря, сортировка вставками отработает за линейное время на любом уже отсортированном массиве - то есть за О(n). И не изменится в зависимости от того, как этот отсортированный массив выглядит. А вот на отсортированных в обратном порядке она будет работать уже за O(n^2), опять же, вне зависимости от его внешнего вида
MaxLich: это не "худший случай", потому что описывает лишь рост функции при росте ее аргумента, но никак не конкретные значения
То есть, пусть сложность алгоритма O(n^2). Это означает, что если мы будем брать поочередно n, увеличивая его постепенно, а время выполнения алгоритма будем рисовать на графике по точкам (абсцисса - n, ордината - время), то получится полу-парабола "вверх". Какая именно - да черт его знает, может, пологая, а может, вверх сразу устремится. Но мы заранее знаем, что каким бы оно там ни было вверху, отработает оно быстрее, чем, например, экспоненциальная функция. Или даже n^3
Askar Fuzaylov: потому что при их обсуждении все скатывается в эмоциональный онанизм, когда люди усилинно плюсуют мнения, аналогичные своему, а минусуют все остальные. В результате рейтинг уже не говорит вообще ни о чем.
На ГТ, например, есть не один десяток (сотня?) товарищей с положительным рейтингом и кармой, которые набили их, высказывая раз за разом одни и те же популярные мнения буквально копипастой под каждой новостью. Люди не то, чтобы им доверяют, они просто так свое мнение продвигают через них. И наоборот, куча людей с отрицательным рейтингом не потому, что им не доверяют, а из-за одного неправильно написанного комментария
snovvcrash: вот это должно было быть в формулировке)
Сейчас я, честно говоря, не придумаю ничего, особенно с примером. Оригинальный AES с нелинейным S-Box'ом в таких ситуациях ломается простым брутфорсом с использованием однозначного маппинга между ОТ и криптограммой. Очевидно, что без известной таблицы такой вариант невозможен - сначала требуется ее (таблицы) перебор.
Однако, если таблица получена в результате линейной функции, между блоками ОТ и криптограммы должна образовываться зависимость (изменение блока ОТ не приводит к сильному изменению блока криптограммы, Шеннон плачет в углу. Пример - 0x0 -> 0x1, 0x1 -> 0x2 ... 0x9->0x10 - все сразу с таблицей понятно). Без данных на руках особо ничего не сказать не могу (да и с ними не факт, что смогу), но посмотреть стоит. Найдя данную зависимость, можно восстановить таблицу аналитически, не применяя ее брутфорс (или применяя его для восстановления лишь части, что куда реальнее). Далее, так как она линейная, то можно прогнать процесс шифрования "в обратку", для известного блока, получив ключ.
На этом все, что сейчас могу сейчас сказать на ночь, дополнительную инфу можно нагуглить по запросу "aes ecb known plaintext attack"
snovvcrash: я правильно понял, размер блока - 8 бит? Если да, то известно ли его разделение (метод) на два 4-битных?
P.S. Не пугай людей странными аналогиями с AES)
Грубо говоря, сортировка вставками отработает за линейное время на любом уже отсортированном массиве - то есть за О(n). И не изменится в зависимости от того, как этот отсортированный массив выглядит. А вот на отсортированных в обратном порядке она будет работать уже за O(n^2), опять же, вне зависимости от его внешнего вида