MB
Рассмотрим текст
AAAAAAAAAAABC
AAAAAAAAAAABC
Код Хаффмана скажет A=0, B=10, C=11. Потратит N+4 бита.
Твой алгоритм скажет, A=00, B=01, C=10 и потратит 2N+4 бита.
Size: a a a
2020 March 18
MB
N - это количество букв А
а
Код Хаффмана скажет A=0, B=10, C=11. Потратит N+4 бита.
Твой алгоритм скажет, A=00, B=01, C=10 и потратит 2N+4 бита.
Твой алгоритм скажет, A=00, B=01, C=10 и потратит 2N+4 бита.
как мой может быть медленнее ? в Коде Хофмана нужно же еще бинарный поиск проводить для каждого символа вроде
A
для большей достоверности - можно чтобы оно было реально вперемешку - N букв A, X букв B и Y букв C в каком-то порядке, причем N > X и N > Y
A
не медленнее же, а больше по размеру
A
естественно код хаффмана медленнее, чем просто передать
A
это трейдофф между скоростью отклика и пропускной способностью. Мы тратим лишнее время чтобы закодировать и декодировать, но зато получаем пакеты меньшего размера, которые могут пролезть через очень тонкий канал/поместиться на очень маленький носитель
/¯
это трейдофф между скоростью отклика и пропускной способностью. Мы тратим лишнее время чтобы закодировать и декодировать, но зато получаем пакеты меньшего размера, которые могут пролезть через очень тонкий канал/поместиться на очень маленький носитель
Поправочка:
Не меньше, а ожидаемо (в среднем) меньше в рамках модели, где распределение символов считается независимым
Не меньше, а ожидаемо (в среднем) меньше в рамках модели, где распределение символов считается независимым
A
да
A
ну собссно известно же, что для любого способа сжатия существует как минимум одна несжимаемая последовательность
SP
здраствуйте ,делаю алгоритм Крускала и для его реализации необходимо проверка на ацикличность при добавлении нового ребра нашел тут код https://e-maxx.ru/algo/finding_cycle ,но немогу понять для чего нужны эти векторы vector<char> cl;
vector<int> p; можите подсказать пожалуйста для чего они
vector<int> p; можите подсказать пожалуйста для чего они
MB
Sergey Polyakov
здраствуйте ,делаю алгоритм Крускала и для его реализации необходимо проверка на ацикличность при добавлении нового ребра нашел тут код https://e-maxx.ru/algo/finding_cycle ,но немогу понять для чего нужны эти векторы vector<char> cl;
vector<int> p; можите подсказать пожалуйста для чего они
vector<int> p; можите подсказать пожалуйста для чего они
Массив p - это дерево обхода.
Массив cl - это метки used.
Но вообще, для краскала этот алгоритм не нужен
Массив cl - это метки used.
Но вообще, для краскала этот алгоритм не нужен
MB
Если писать его вот так, получится асимптотика VE.
А если на системе непересекающихся множеств, то E log V.
А если на системе непересекающихся множеств, то E log V.
A(
Если писать его вот так, получится асимптотика VE.
А если на системе непересекающихся множеств, то E log V.
А если на системе непересекающихся множеств, то E log V.
не V^2?
A(
а, сори, там просто дфс
MB
не V^2?
Да, ты прав. Но это нужно еще отсечение поставить.
MB
Но все равно хуже чем E log V.