Ребят, небольшой оффтоп В ют увидел алгос из собеса и на

Question

Ребят, небольшой оффтоп В ют увидел алгос из собеса и на

скрине один из вариантов решения, но автор утверждает сложность O(n), когда общая сложность O(n+n^2+n) == O(n^2) потому, что из-за слайса [1 1 1 1 1] во вложенном цикле в худшем случае будет n^2
Сложность этого алгоса действительно O(n) или мои утверждения верны и сложность O(n^2)?

#backend #embedded #programming #russian #rust

0

26.05.2023

3 ответов

15 просмотров

Danil Mosolov Автор вопроса

Mikail Bagishov
в коде три цикла. первый делает O(len(citations)) ...

Получается n^2

0

26.05.2023

Αλεχ Zhukovsky

у тебя тут средний множитель не N^2 а некий N*C где C завиисит от содержимого массива. Оценки о большие\малые не должны иметь зависимость от содержимого данных, только от их размера

0

26.05.2023

Mikail Bagishov · Accepted Answer

Mikail Bagishov

в коде три цикла. первый делает O(len(citations)) работы второй O(сумма count), что опять же O(len(citations)) Третий O(n), т.е. O(len(citations)) итого звучит как линия

0

26.05.2023

172 похожих чатов

Ребят, небольшой оффтоп В ют увидел алгос из собеса и на

3 ответов

Похожие вопросы