ПФ
поиск элемента — логарифмическая солжность
Size: a a a
2020 July 11
ПФ
я вот прям не уверен что поиск элемента медленнее деградирует чем добавление в начало массива
S
В пределе любое копирование элементов - O(n)
λ
Я бы прям не поручился тут за ответ, бенчмаркать надо
Не надо бенчмаркать, там ж про рост.
S
Да, естественно System.arrayCopy при достаточно малых массивах от n не зависит, но вопрос про рост.
ПФ
Проблема в том, что там тоже не линейный рост
λ
Где там
ПФ
При копировании массивов
ПФ
Копируется страничка за одну операцию
λ
Эт не важно
ПФ
А вот этот вопрос явно некорректно сформулирован
λ
Big o notation никак не учитывает особенности реализации, у тебя может быть O(n), который работает быстрее O(Logn), но рост первого очевидно быстрее
ПФ
Понятно что тут любой из GET сработает — вопрос в API
ПФ
Big o notation никак не учитывает особенности реализации, у тебя может быть O(n), который работает быстрее O(Logn), но рост первого очевидно быстрее
Это правда, да. Жалко только что она абстрактная и мало чего говорит о реальности
λ
Лул, а где вариант graphql
ПФ
В Big O, когда мы говорим о программировании мы предполааем, что деление выполняется за константу, но на самом деле нет…
λ
Понятно что тут любой из GET сработает — вопрос в API
Выбирай 3
ПФ
Выбирай 3
Так и сделал, получил A
ПФ
Но мне вопросы и про амортизационный анализ, и про вот это вот API кажутся неправильыми
R
Big o notation никак не учитывает особенности реализации, у тебя может быть O(n), который работает быстрее O(Logn), но рост первого очевидно быстрее
Аниме такое есть, Big O