Оцениваем сложность алгоритмов на C# по памяти и времени с примерами

[LinarMast]

Но на самом деле, нет — в данном случае на вход просто подается N * M элементов и время пропорционально N * M, то линейное O(n).

Возник вопрос к правилу 4.
Почему пишете, что время линейное, хотя до этого правильно указали сложность O(N * M), все таки итерация проходит по двумерному массиву.

[mayorovp]

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

[sdramare]

Потому что сложность апроксимируется сверху линейной функцией.

[ignorance]

В методе 2 указателей еще if (sum < target) нужно?

[andrey_stepanov1]

Спасибо за поправку - добавили

[aleksandernekr]

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++)

[andrey_stepanov1]

Спасибо, при верстке кода со скринов наделал ошибок — вроде все исправил

[Alexandroppolus]

Правило 4 применимо для простого кейса - когда сложность внутреннего цикла не зависит от текущей итерации внешнего. Если зависит, то придется аккуратно просуммировать сложности, и там может выйти по разному. Например, в пузырьковой сортировке так и остается O(N^2), а вот для того же heapify внезапно оказывается O(N)

[andrey_stepanov1]

Да — именно это как раз пытался показать в Примере с подвохом.

[Alexandroppolus]

в этом примере несколько другое. А именно, что конкретно брать за "N" в О-большом. Если длину стороны матрицы, то так и будет O(N^2)

[nronnie]

нас может ввести в заблуждение массив данных data неизвестной размерности

Наверное, все-таки, размера а не размерности - лучше поправьте.

[dyadyaSerezha]

Но внутри вызывается функция Alg4() из предыдущего примера

Предыдущий Alg4 принимает двумерный массив. А вот предпредыдущий - одномерный. У вас два Alg4. Поправьте.

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

[andrey_stepanov1]

Да, запутал с одинаковыми названиям Alg4, сейчас исправил. Добавил верное замечание про CPU — спасибо!

[piton369]

В 5 примере странно, я не вижу O(n^3) в этой строке:
что сложность этого алгоритма — O(n^3) при всей его визуальной минималистичности.

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

[mayorovp]

Там картинка с alt-текстом, у вас не прогрузилась картинка, а при копировании в буфер попал alt-текст.
Почему картинка не прогрузилась - выясняйте сами.

[piton369]

Так это не в моей статье косяк, зачем мне выяснять? Я заметил - сообщил, автор захочет - исправит.

[mayorovp]

Косяк как раз на вашей стороне, потому что эту картинку я вижу.

[MaNaXname]

Решение 4
не хватает кода после return идут {}

[andrey_stepanov1]

В последней строке?

[MaNaXname]

а ну вот поправили добавив
if (sum < target)
теперь стало понятно что код работает