Телеграмм чат группы math

ну опять же, нужно смотреть как там в теории алгоритмов на самом деле, я не шарю. По идее, там входные данные это n элементов массива (всмысле, во всяких реализациях типа бинпоиска), поэтому такая сложность вроде как осмысленная... А насчёт одной переменной я хз

источник

12:34пожаловаться #4

Nephilim in Physics.Math.Code

хм а ну да
ну там и задача простецкая

источник

12:34пожаловаться #5

qwerty in Physics.Math.Code

Допустим, вы выполняете запросы get к вашей хеш-таблице, получаете за константу, не пртвязываясь к количесьву данных

источник

12:34пожаловаться #6

Tim Reizin in Physics.Math.Code

Ну на пользовательском уровне, если на входе есть одно число n, то говорят что там сложность sqrt(n), если базовая проверку на простоту, например(то есть просто пример)

источник

12:36пожаловаться #7

Nephilim in Physics.Math.Code

в общем алгоритмы которые с увеличением данных не растут а мало того и уменьшаются в скорости кажутся мне сказкой

источник

12:36пожаловаться #8

пп

п п in Physics.Math.Code

Аа, да. Круто, я и не подумал.

источник

12:37пожаловаться #9

qwerty in Physics.Math.Code

Вообще, можно делать запросы с определенной асимптотикой, не обязательно оперировать в терминах решения самой задачи...

источник

12:37пожаловаться #10

Tim Reizin in Physics.Math.Code

Ну если вот такое использовать(ну в сп это точно норма) то не сказка @hybrid_nephilim

источник

12:37пожаловаться #11

Nephilim in Physics.Math.Code

хз тогда и задача должна быть банальная

источник

12:38пожаловаться #12

пп

п п in Physics.Math.Code

@V_an96. Короче скользкая тема, я ливаю, потому что надо уже вдаваться в полные формальности

источник

12:38пожаловаться #13

Nephilim in Physics.Math.Code

я думаю все зависит от задачи
для каждой задачи есть свой быстрый предел

источник

12:40пожаловаться #14

Nephilim in Physics.Math.Code

например как дискретное преобразование фурье со сложность n^2
можно ускорить до n*ln(n), но для этого нужно 2^n элементов и немного упрощеный алгоритм а не как любое число элементов в дискретном преобразовании

источник

12:42пожаловаться #15

Viαη in Physics.Math.Code

источник

12:43пожаловаться #16

Alexander in Physics.Math.Code

какие ещё 2^n элементов? если бы их было нужно, то алгоритму пришлось бы их использовать, потратив на каждый хотя бы такт. тогда время работы было бы минимум 2^n, а вовсе не n*log(n).
вы путаете, n там и правда бывает степенью двойки, но уже другого числа, скажем, k. но есть алгоритмы и на другие длины, когда среди множителей есть тройки, пятёрки, семёрки. с той же асимптотикой.

источник

13:16пожаловаться #17

Nephilim in Physics.Math.Code

есть но я как пример привел

источник

13:17пожаловаться #18

Nephilim in Physics.Math.Code

n и k в данных преобразованиях равны ибо они обратимы

источник

13:18пожаловаться #19

Alexander in Physics.Math.Code

но при этом помнят, что он экспоненциальный 🤣
поскольку на входе у нас log(n) бит.

источник

13:18пожаловаться #20