|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
04.11.2011, 22:42 | #1 |
Пользователь
Регистрация: 16.03.2010
Сообщений: 13
|
Алгоритм линейный по скорости и константный по памяти
Не могли бы вы пояснить что это именно такое?
|
05.11.2011, 01:58 | #2 |
Старожил
Регистрация: 25.10.2011
Сообщений: 3,178
|
Пусть у нас есть задача, входные данные для которой могут иметь различный объём - один символ, десять, миллион, миллиард. Обозначим число входных символов как n.
Как правило, время выполнения алгоритма и требуемая в процессе память зависят от n: фотографию 640х480 Windows открывает меньше секунды, а вот 12000х10000 может заставить задуматься. Обозначим зависимость времени от n как T(n), зависимость максимальной требующейся в процессе выполнения памяти от n как M(n). Под F(n)=O(g(n)) обычно понимают, что существует некоторые фиксированные, не зависящие от n числа A и B, оба строго больше нуля, такие, что при всех n (как вариант, при всех n больше некоторого m) A<F(n)/g(n)<B. Так, например, n^2+3n+15=O(n^2); 1+n/1000000=O(n). Линейным по скорости называется алгоритм, для которого T(n)=O(n). Константным по памяти - такой, для которого M(n)=O(1). |
05.11.2011, 11:04 | #3 |
Пользователь
Регистрация: 16.03.2010
Сообщений: 13
|
Спасибо =)
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
линейный алгоритм в дельфи | dearkato | Помощь студентам | 0 | 24.10.2011 18:50 |
Линейный алгоритм ) | ProgrammiST-_- | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 07.10.2011 21:16 |
линейный алгоритм | Seregga | Помощь студентам | 2 | 04.01.2011 11:20 |
Линейный алгоритм | Alexandra1991 | Помощь студентам | 7 | 18.10.2010 23:12 |
pascal 7, линейный алгоритм | prostac | Помощь студентам | 3 | 18.12.2009 21:21 |