Форум программистов, компьютерный форум CyberForum.ru

Вычислительная сложность CRC32 - C++

Восстановить пароль Регистрация
 
4erniikvadrat
0 / 0 / 0
Регистрация: 05.08.2013
Сообщений: 16
20.08.2013, 12:01     Вычислительная сложность CRC32 #1
Какова вычислительная сложность алгоритма CRC32? N^2 или NlogN или еще что-то?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
20.08.2013, 12:05     Вычислительная сложность CRC32 #2
4erniikvadrat, линейная
4erniikvadrat
0 / 0 / 0
Регистрация: 05.08.2013
Сообщений: 16
20.08.2013, 12:09  [ТС]     Вычислительная сложность CRC32 #3
а можно какую-нибудь ссылку? я ничего не смогла найти стоящего на этот счет
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
20.08.2013, 12:51     Вычислительная сложность CRC32 #4
Цитата Сообщение от 4erniikvadrat Посмотреть сообщение
а можно какую-нибудь ссылку?
У меня ссылки тоже нет. Но можно просто взглянуть на табличную реализацию алгоритма.
Каждый байт исходной последовательности обрабатывается за константное время, то есть О(1). Таким образом сложность напрямую зависит исключительно от длины исходной последовательности, а это и есть О(n).
4erniikvadrat
0 / 0 / 0
Регистрация: 05.08.2013
Сообщений: 16
20.08.2013, 14:07  [ТС]     Вычислительная сложность CRC32 #5
Спасибо!
Yandex
Объявления
20.08.2013, 14:07     Вычислительная сложность CRC32
Ответ Создать тему
Опции темы

Текущее время: 02:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru