Можете пожалуйста объяснить про ассимптотическую сложность? Есть этот псевдокод, он похож

на С язык но это не так важно:

Algorithm Add (A,B,n)
{
for ( i = 0; i < n; i++)
{
for (j = 0; j < n; j++) {
C[i,j] = A[i,j] + B[i, j];
}
}
}

Автор этого видео https://www.youtube.com/watch?v=1U3Uwct45IY с 5.37 до 6.44 говорит что реальная сложность этого кода 2n^2 + 2n + 1 - он правt? Везде на сайтах написано что в питоне асимптотическая сложность 2х вложенных циклов n^2, и также не понимаю почему этот кусок кода C[i,j] = A[i,j] + B[i, j]; у него имеет сложность n - автор говорит что все что в цикле фор выполняется н раз, но во всех других источниках говорится что у таких операций асимптотическая сложность - О(1)

Уже несколько часов смотрю это видео и не могу понять, прав ли автор или нет? Тоесть меня интересует прав ли он в реальной сложности кода, из которой он правильно выводит асимптотическую сложность н^2 в чем я согласен

Математика, злая ты .... O(2*n*n +2*n +1) == O(n*n)

n*n это факториал n! ? Значит автор видео не прав?

а нет, что я несу, это n^2

Вижу два вложенных цикла фор - перемножая их длину.

спасибо, да асимптотическая O*n^2) да, согласен, а про реальную сложность O(2*n*n +2*n +1) он прав?

Вообще выглядит очень странно

Это весьма расплывчатая штука в реальных условиях. Проблема в том, что разные операции не эквивалентны, чтобы их можно было просто посчитать и что-то полезное получить.

Но если упрощённо считать их одинаковыми, подсчет со скина разве верен?

Лень вникать в бессмысленные действия. Но там явно не все операции учтены.

М, начинаю понимать. Обычно видимо операциями инкремента i и j пренебрегают и смотрят только что происходит в теле цикла

Мне этот мужик напомнил вэб сарвар...

C[i,j]=A[i,j]+B[i,j] это уже что-то около десятка или больше действий.

А учитывал что умножение сложнее сложения?

Мы в волшебном мире, где есть единороги, операции одинаковые и нет регистров и кэша процессора.

Забавный эффект кстати возможкн если циклы местами поменять

Для асимптотической сложности 2n^2 + 2n + 1 эквивалентно n^2

спасибо, да, это знаю. Меня интересовало его расчеты 2n^2 + 2n + 1 верны или нет - тут сказали что неверны вообще

Ну в твоем коде ровно n^2 операций

Почему? Если увеличение переменных цикла и проверку условий учитывать, вроде формально всё оказывается верно

Там ровно два цикла которые range(n) обходят

Как я понял, верны, если считать все операции которые он перечислил атомарными и давать им одинаковый "вес" в подсчете

Хз правда какую полезную информацию такая дичь дает

а обычно считаем действия не атомарными? Вот например https://proglib.io/p/slozhnost-algoritmov-i-operaciy-na-primere-python-2020-11-03 тут в начале или тут https://www.yuripetrov.ru/edu/python/ch_06_01.html в серединке - дан список действий (для списков, кортежей, массивов, словарей) и их сложность - такие списки можно считать атомарностью?

по-моему тоже скорее путают, но мб и полезно понять что мы их отбрасываем именно потому что асимптотически ничего не меняют

я хотел глубже понять ассимптотику с константами чтобы в дальнейшем лучше код писать, смотреть что можно отбросить или сократить и снова сравнивать, а оказывается что не стоит так глубоко копать и просто как все норм программисты смотреть на n^2 или log n и т.д. Спасибо что ответил

имел в виду действия которые там считают (например при добавлении в список доступ к элементу, сдвиг на 1 и подобное — обычно всем действиям дается одинаковый "вес" при подсчете сложности (а, например, сложение оч больших чисел нельзя считать атомарным, но тема сложная — как именно понять что можно что нельзя таким считать сходу не соображу

Ты отбрасываешь любое умножение на константу, а при сложении выбираешь слагаемое которое быстрее всех растет, все

понял, т.е. например Получение элемента l[i] O(1) Удаление элемента (del) del l[i] O(N) Проверка наличия x in/not in l O(N) Линейный поиск в списке это атомарность - у каждого действия такой-то вес и считаем по таким формулам

спасибо

так как (n^2) больше O(n), то O(n) просто отбрасывается, поэтому O(n^2 + n) -> O(n^2) операция присвоения же имеет O(n) потому что списки это не массивы и под капотом там посложнее операция чем "возьми указатель на начало списка и в адрес равный начало+индекс*размер ячейки положи значение"

спасибо!

нет, присвоение константное, там квадрат п.ч он считает сколько всего приссвоений

https://wiki.python.org/moin/TimeComplexity там c++ но не важно, присвоение уже выделенному участку

пасиб, думал оно медленней, тогда не прав