Ну я понимаю что базу можно выбрать любую.
Просто хотел проверить правильно ли я понимаю что сложность будет такая же ( но скорее всего константа лучше) как и у построения отсортированного дерева только не бинарного а 2^7,8,9… Ичного?
Тогда поправьте меня если я не прав, но ваше решение использует байтовое разложение числа а не битовое и именно по этому ваша сложность приблизительно n * log_256 (Max)?
Подскажите пожалуйста, я правильно понимаю что ваша сортировка выигрывает грубо говоря когда количество проходов k (оно же количество битов в элементах) грубо говоря меньше чем log (n)?
И если это так, то получается что все элементы массива можно воспринимать как числа от 0 до n (или до 2n при округлении логарифма вверх), а значит линейная сортировка будет прекрасно работать?
Мне просто нравится решать подобные задачки. Сорри написать красиво не мог — только зарегался, табуляция вроде как не работает, не говоря уж на latex формулах.
Каждому кажется что его решение намного проще =)
На счет решения самого уравнения… Оно решается без графиков
x = a(x//b) + c
просто умножить обратно на b:
bx = a(x-r)+bc, где r это остаток х при делении на b
перенося х в одну сторону получаем
x(b-a) = -ar + bc= r(b-a) + b(c-r)
предполагая что b!=a (иначе решение очевидно)
x = r + b * (c-r)/(b-a)
т.е. r это любое число от 0 до b вида
r = c mod (b-a) + k(b-a)
а само число х:
x = (bc — ar) / (b-a)
Чтоб выбрать минимальное х нужно просто взять максимальное r, т.е. максимальное k
ну так там выходит порядок влияния этого импульса как ~p/c.
по той же причине мы и складываем скорость v1+v2, а не релятевиской формулой.
Ну я понимаю что базу можно выбрать любую.
Просто хотел проверить правильно ли я понимаю что сложность будет такая же ( но скорее всего константа лучше) как и у построения отсортированного дерева только не бинарного а 2^7,8,9… Ичного?
Тогда поправьте меня если я не прав, но ваше решение использует байтовое разложение числа а не битовое и именно по этому ваша сложность приблизительно n * log_256 (Max)?
Я говорю не о вашем алгоритме, а о предполагаемых данных. Я правильно понимаю что количество бит в них порядка log(n)?
Подскажите пожалуйста, я правильно понимаю что ваша сортировка выигрывает грубо говоря когда количество проходов k (оно же количество битов в элементах) грубо говоря меньше чем log (n)?
И если это так, то получается что все элементы массива можно воспринимать как числа от 0 до n (или до 2n при округлении логарифма вверх), а значит линейная сортировка будет прекрасно работать?
A/(S_i' d) \in N
к выражению
S_i' = A / (N d) > 1
нет никакой математики…
Каждому кажется что его решение намного проще =)
x = a(x//b) + c
просто умножить обратно на b:
bx = a(x-r)+bc, где r это остаток х при делении на b
перенося х в одну сторону получаем
x(b-a) = -ar + bc= r(b-a) + b(c-r)
предполагая что b!=a (иначе решение очевидно)
x = r + b * (c-r)/(b-a)
т.е. r это любое число от 0 до b вида
r = c mod (b-a) + k(b-a)
а само число х:
x = (bc — ar) / (b-a)
Чтоб выбрать минимальное х нужно просто взять максимальное r, т.е. максимальное k