Помогите оценить сложность алгоритма поиска одинаковых 4рех чисел в массиве , вычислительная сложность: лучший, средний и худший случаи

[FasterHarder]

Всем хай! Сходу к делу!

Есть такая задачка: дан одномерный массив А, состоящий из N целых чисел. Проверить, есть ли в этом массиве хоть одна 4рка одинаковых элементов. Оценить сложность алгоритма.


Сразу договоримся, что массив уже заполнен и идет непосредственно поиск. И речь идет про оценку вычислительной сложности (временной), а не пространственной (про память, т к здесь память дополнительная не юзается и все происходит "in place" - на месте)
Вот фрагмент кода (псевдокода), который ищет первую 4рку одинаковых элементов:

for ( int i = 0; i < n - 3; i++ )
    for ( int j = i + 1; j < n - 2; j++ )
    {
        if ( a[ i ] == a[ j ] )
            for ( int k = j + 1; k < n - 1; k++ )
            {
                if ( a[ i ] == a[ k ] )
                    for ( int l = k + 1; l < n; l++ )
                    {
                        if ( a[ i ] == a[ l ] )
                            return ...;     // первая четверка одинаковых чисел найдена
                    }
            }
    }
 
return ...;     // среди элементов массива a длины n нет ни одной четверки одинаковых чисел

Это брутфорс (полный перебор всех возможных четверок). И пусть это неоптимальное решение(алгоритм), но хочется обсудить именно этот вариант.

а) Какой здесь лучший случай? Как я понимаю, когда 4рка элементов есть и она находится в самом начале массива. В этом случае сложность О(1)? операциями типа i = 0, j = i + 1 и пр. пренебрегаем, хотя, даже если их учесть, там будет что-то О(4) или О(8), что все равно запишем, как О(1)
б) Какой здесь худший случай? Это когда в массиве нет ни одной 4рки одинаковых элементов и тогда все 4ре цикла будут работать ОТ и ДО и получим (n - 3) * (n - 2) * (n - 1) * n ~ N^4, хотя формула здесь не совсем такая будет, т к счетчики j, k, l идут не от 0, но на асимптотике это не сказывается итоговой, как я понимаю, поэтому сложность O(N^4) - полином 4ой степени.
в) Какой здесь средний случай? Этот момент вызывает больше всех вопросов! В теории не смог найти объяснения такого поведения алгоритма.
Если посчитать среднее как полусумму концевых случаев (лучшего и случая), то вроде будет бред, т е Oср = (O(1) + O(N^4))/2 --> N^4, т к коэффициентами пренебрегаем. Если так и можно посчитать, значит, я ошибся при получении лучшего случая и там не О(1)...
Итак, как считать средний случай.
1. При запусках предполагаем, что в одном запуске есть 4рка чисел, в другом нет (для второго случая сложность О(N^4) )
2. Если 4рка есть, то берем ее по центру массива, в этом случае i успевает пробежать от 0 до N/2 (грубо если), ну, в принципе остальные счетчики аналогично (оч.грубо если), т е N/2 и получаем N/2 * N/2 * N/2 * N/2 = (N/2)^4 = N^4/8 ---> N^4 и снова что ли N^4 Не кажется ли это странным?) хм..
Говорят, что средняя сложность такого алгоритма в районе O(N^2), но как ее получают??? Подскажите, плиз
------------------------------------------
Понятно, что для поиска хотя бы одной 4рки сначала стоит упорядочить массив. Ок, кратко разберем этот вариант.
а) сортируем массив А. Любым способом. Сложность О(алгоритм выбранной сортировки)
б) а затем интересный момент. Не уверен, что дальше будет сложность линейного перебора за время О(N), хотя, если пренебречь проверками аля (a[i] == a[i + 1] && {a[i] == a[i+2]...), то, тогда вроде будет О(n)
и итоговая сложность алгоритма:
1. лучший случай: О(алгоритм выбранной сортировки) * О(1)
2. худший: O(n) + O(алгоритм выбранной сортировки)
3. средний случай: O(n/2) + O(алгоритм выбранной сортировки) ----> почти худший случай, хм.. разница вроде совсем не велика на величину N/2

Поясните, плиз, за эти рассуждения, буду оч.признателен.
спс. за внимание..

Сообщение отредактировано: FasterHarder - 18.02.22, 12:58

[Akina]

Цитата FasterHarder @ 18.02.22, 12:56

Говорят, что средняя сложность такого алгоритма в районе O(N^2), но как ее получают???

Какую только хню не говорят... не верь.

Средняя температура по больнице - вообще неблагодарная вещь. Поэтому ВООБЩЕ средний случай оценить практически нереально. Но попробуем оценить сложность, когда заведомо есть строго одна четвёрка.

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

Сколько раз отработают циклы?

Каждый из циклов отработает N раз (множитель, как обычно, опускаем).

При этом до "донышка" на каждом цикле мы дойдём (как обычно, опускаем степени нижнего порядка) N³, N², N и 1 раз соответственно. Сумма - (опять опускаем степени нижнего порядка) N³.

Общая сложность = O(N * N^3) = O(N^4).

Цитата FasterHarder @ 18.02.22, 12:56

Понятно, что для поиска хотя бы одной 4рки сначала стоит упорядочить массив. Ок, кратко разберем этот вариант.

Лучшие алгоритмы сортировки дают O(N*logN). Последующий поиск четвёрки не хуже O(n). Их сумма - O(N*logN).

Добавлено 18.02.22, 14:33
PS. Ещё обоснование O(n^4). Если количество чисел увеличить в K раз, то среднее местоположение (позиция в списке) каждого числа увеличится в K раз. Соответственно количество итераций внешнего, наиболее затратного, этапа, до нахождения первого из чисел увеличится в K раз, количество внутренних итераций в K^3 раз, а всего количество увеличится в K*K^3=K^4 раз.

Сообщение отредактировано: Akina - 18.02.22, 14:33

[FasterHarder]

Цитата Akina @ 18.02.22, 14:26

Поэтому ВООБЩЕ средний случай оценить практически нереально.

именно поэтому при оценке сложности алгоритма берут ХУДШИЙ случай? Если, да, то почему, когда говорят про Quick Sort берут за основу О(n * log(n)), хотя у нее худший случай, как, например, у сортировки выбором, т е О(n^2)?

Цитата Akina @ 18.02.22, 14:26

Каждый из циклов отработает N раз (множитель, как обычно, опускаем).

При этом до "донышка" на каждом цикле мы дойдём (как обычно, опускаем степени нижнего порядка) N3, N2, N и 1 раз соответственно. Сумма - (опять опускаем степени нижнего порядка) N3.

вот этот момент вот не совсем понял вроде) ПОЧЕМУ (точнее, ЗАЧЕМ) берем СУММУ, они ведь выполняются не последовательно, а вкладываются 1 в другой? хм...Я к тому, что вложенные циклы ведь перемножают, а не суммируют...Зачем доказывать через сумму вложенные циклы? А то, что цикл по i отработает 1 раз, цикл по j отработает i*N = 1*N = N раз, цикл по k отработает i*j*N = N^2 и т.д. понятно.

Цитата Akina @ 18.02.22, 14:26

Лучшие алгоритмы сортировки дают O(N*logN). Последующий поиск четвёрки не хуже O(n). Их сумма - O(N*logN).

точно, ведь из суммы выбирают самый "тяжелый" множитель, а это будет О(для сортировки) и сложностью О(n) можно пренебречь (особенно при возрастающем n)

[MIF]

Имо, упорядочение всех отрезков по длине и сканирование полученного листа быстрее полного перебора всех точек.
В вырожденном случае, когда все точки находятся в одной позиции, вариант с упорядочиванием будет чуть медленнее, в общем случае он быстрее. Его сложность О(n* log(n) меньше O(n^5).

[MIF]

Надо отметить, что упорядочивание листа - не самая медленная операция. Составление листа медленнее перебора. Его сложность О(n^2)

[MIF]

Если алгоритм сбора всех отрезков и их упорядочивания быстрее алгоритма проверки на квадрат, то поиск всех отрезков, их упорядочивание и проверка групп отрезков на квадрат будет быстрее сбора всех четырехугольников и проверки их на квадрат.

[MIF]

Предлагаю следующий алгоритм:
Проверка всех точек на совпадение их координат и об’единение совпадающих;
Нахождение всех отрезков;
Упорядочивание их по длине;
Проверка отрезков одинаковой длины на квадрат;
Если надо посчитать совпадающие квадраты, то для каждого квадрата со сгруппированными точками найти все совпадающие квадраты.

[FasterHarder]

MIF, тут как бы это, мы обсуждаем вычислительную сложность текущего алгоритма, т е не нужен никакой новый алгоритм), но за предложение спс), все когда-нибудь пригодится

-----------------------------
Akina, еще есть такие моменты (их много, поэтому заберу у тебя не оч.мало времени на все моменты).
Кроме О, есть обозначения ТЕТТА, СИГМА (и их строчные аналоги). Кстати, еще есть о-малое, но там совсем туманно, оно вроде отвечает за точную оценку сложности, но точную оценку практически невозможно получить...
-------------------------------

О-большое - верхняя оценка, как я понимаю, т е ХУЖЕ этой оценки алгоритм НЕ сможет работать. Означает ли это, что в этом случае надо брать ТОЛЬКО худшие случаи оценки всех входящих алгоритмов в состав более сложного алгоритма? Опять на примере qsort, худшее поведение ее О(N^2), поэтому надо брать именно его, но ВЕЗДЕ берут средний случай O(n * log(n)), но это ведь неправильно?) Т е можно брать n * log(n), но тогда не нужно писать О-большое получается, хм...
---------------------------------

Насколько ТЕТТА-большая реально пригождается при анализе? Такое впечатление, что можно не обращать внимание, т к все равно реальную сложность алгоритма не отражает (обычно совпадает с О-большое).
----------------------------------

СИГМА-большое - по факту берет на оценку ЛУЧШИЕ случаи работы алгоритма, т е ЛУЧШЕ этой оценки алгоритм НЕ сможет работать. На практике оказывается бесполезным, т к полагаться исключительно на лучшие исходы, как минимум глупо? Еще есть сигма-малое, но там нестрогое проверяется что-то, т е почти аналог СИГМА-большому.
---------------------------------

При анализе сложности алгоритмов достаточно ВСЕГДА концентрироваться только на О-большом (худшее поведение) и не обращать внимания на остальных "греков" (ТЕТТА-малое-большое, СИГМА-малое-большое, о-малое)?
---------------------------------

Анализ сложности алгоритма в принципе уместен только тогда, когда есть циклы и рекурсия? Если есть набор простых линейных действий, то сложность автоматически становится О(1)? Пример: "надо найти корни квадратного уравнения". ПОлучается сложность этого алгоритма О(1)??? Операции типа "+,-,*,sqrt..." принимаем за выполняющиеся мгновенно за О(1) и получается сумма операций сложности О(1) дает в результате также О(1)?? Но в реальности все равно какое-то процессорное время они заберут, но этим пренебрегаем.
---------------------------------

Akina, ведь можно прикинуть "на глазок", сколько времени будет выполняться тот или иной алгоритм в сек. например. Сколько ты в реальности принимаешь способность процессора выполнять элементарных инструкций 10^7, 10^8, 10^9, 10^10 за секунду?? Например, если есть сортировка пузырьком со сложностью О(N^2), то можно примерно прикинуть, при каком N время работы составить около 1 секунды. Например, если берем процессор со 10^8 операций в секунду, то получаем N ~ sqrt(10^8) = 10 000 элементов, т е, если взять 10 100 элементов, то время работы программы может перевалить за 1 сек. Как делаешь такую оценку или нет в этом необходимости в принципе?? Какую скорость в сек. для программы считаешь приемлемой в критических случаях?
----------------------------------

Согласен с утверждением, что, если в программе небольшое N (элементов, например = 100), то алгоритм оказывается в принципе не важен, имеется в виду, не экспоненциальные случаи (типа N!), а полиномиальные, т е в принципе N^2 (10 000), N*log(N) = 100 * 8 = 800, N * log(N)^2 = 6 400 и др. с точки зрения производительности процессора они все будут выполняться "почти" мгновенно?
----------------------------------

Все, что мы рассматриваем в этом топике можно отнести к введению в анализ алгоритмов, т е это 1-2 класс по 11годовой программе (условно). Теория ушла далеко вглубь в этой области и там начинается чертовщина лютая на каком-то этапе, т е там уже задают на вход не просто N, а всякие функции, какая-то подвязка идет P, NP, какие-то коэффициенты альфа вводят, уже не просто N^k, a N^k' и пр. пр. Насколько нужно это все дело изучать глубже или достаточно хотя бы основательно понимать эту базу (1-2 класс)? Интересует твой ответ с высоты опыта. А так понятно, что чем больше знать - тем лучше))

Akina, спс за внимание) при возможности пробегись по всем вопросам(моментам), хотя бы кратко.

[AVA12]

Цитата

Лучшие алгоритмы сортировки дают O(N*logN)

Протестую! Поразрядная сортировка требует O(N), а "быстрая поразрядная", к тому же, делается "на месте".

[Akina]

Цитата FasterHarder @ 19.02.22, 05:52

Кроме О, есть обозначения ТЕТТА, СИГМА (и их строчные аналоги). Кстати, еще есть о-малое, но там совсем туманно

Ну для начала так: ссылка 1, ссылка 2

Цитата FasterHarder @ 19.02.22, 05:52

Как делаешь такую оценку или нет в этом необходимости в принципе?? Какую скорость в сек. для программы считаешь приемлемой в критических случаях?

Да я вообще не программист и программ не пишу! у меня терпежу никогда не хватает на такие длинные задачи.
Сетевой админ я...

Сообщение отредактировано: Akina - 19.02.22, 17:33

[FasterHarder]

понял, спс. за ссылки