Комментарии 20
Но на самом деле, нет — в данном случае на вход просто подается N * M элементов и время пропорционально N * M, то линейное O(n).
Возник вопрос к правилу 4.
Почему пишете, что время линейное, хотя до этого правильно указали сложность O(N * M), все таки итерация проходит по двумерному массиву.
В методе 2 указателей еще if (sum < target) нужно?
private vpid Alg2(int[]data, int target)
Опечатка: нужно void.
В 3 примере:
data.Lenght
Ещё i в цикле не инициализирована
for (i , data.Lenght; i++) // O(n)
В 4 правиле нужно data и for
for (int i = 0; i < dana.Lenght; i++)
{
fir (int j = 0; j < data[i].Lenght; j++)
Правило 4 применимо для простого кейса - когда сложность внутреннего цикла не зависит от текущей итерации внешнего. Если зависит, то придется аккуратно просуммировать сложности, и там может выйти по разному. Например, в пузырьковой сортировке так и остается O(N^2), а вот для того же heapify внезапно оказывается O(N)
нас может ввести в заблуждение массив данных data неизвестной размерности
Наверное, все-таки, размера а не размерности - лучше поправьте.
Но внутри вызывается функция Alg4() из предыдущего примера
Предыдущий Alg4 принимает двумерный массив. А вот предпредыдущий - одномерный. У вас два Alg4. Поправьте.
Ну и общее замечание - из-за активного кеширования у современных CPU многие классические оценки часто не работают вплоть до размеров данных в несколько К элементов. Надо тестировать.
В 5 примере странно, я не вижу O(n^3) в этой строке:
что сложность этого алгоритма — O(n^3) при всей его визуальной минималистичности.
но когда я скопировал эту строку для того чтобы указать на опечатку, сюда оно скопировалось.
Может это проблема на моей стороне.
Решение 4
не хватает кода после return идут {}
Оцениваем сложность алгоритмов на C# по памяти и времени с примерами