Я читаю книгу под названием « Принципы информатики» (2008) Карла Рейнольдса и Пола Тиманна (опубликована в «Схемах Шаума»).
Во второй главе представлены алгоритмы с примером последовательного поиска, который просто перебирает список имен и возвращает TRUE, если в списке найдено данное имя.
Автор продолжает (стр. 17):
Мы говорим, что «порядок роста» алгоритма последовательного поиска равен n. Обозначения для этого T (n). Мы также говорим, что алгоритм, порядок роста которого находится в некотором постоянном множителе T (n), имеет тета NL скажем. «Последовательный поиск имеет тета n». Размер проблемы n, длина списка, в котором выполняется поиск.
Мне действительно трудно это понять. Книга изобилует ошибками, поэтому я не уверен, что я что-то упустил или есть опечатка в параграфе выше. В общем английском я редко вижу, чтобы любое предложение заканчивалось на «... сказать».
Я очень смущен.
Что означает Т? Книга не объясняет. Это для времени или для тета?
Если «тета NL» означает «Последовательный поиск имеет тета n». Что означает L? «Линейный» или «длина»?
Я написал издателям с просьбой объяснить. Они сказали, что отправят мое сообщение авторам. Они не ответили. Я также пытался взглянуть на другие источники, но у меня все еще возникает мучительное чувство, что я что-то неправильно понимаю - поэтому не могу успокоиться, пока не расшифрую этот параграф.
Если у кого-то есть копия этой книги, и он понял этот пункт. Тогда я был бы признателен, если бы вы сообщили мне, если этот абзац точен, или объясните его другими словами. Благодарю.
Ответы:
Абзац неверный. К сожалению, это похоже на то, что студент, который не понимает материала, написал бы в качестве ответа на упражнение. Такого рода глупости нет места в учебнике. Не делайте резких движений. Положи книгу. Отойди от книги.
Это явно было искажено. Я думаю, что авторы намеревались написать что-то вроде:
Но, пожалуйста, мы не говорим «имеет тета », так же как, если - это ваша запись для роста, вы бы не сказали «Джон имеет 180 см». Это просто неправильная форма слов. На самом деле мы говорим: «Время выполнения алгоритма - тета (или тета )». В частности, обратите внимание, что - это инструмент для обсуждения математических функций, а не алгоритмов. Тета не означает, что время выполнения - это нечто; скорее это то, что вы можете использовать, чтобы говорить о времени выполнения.ч ч н н ΘN час час N N Θ
Между прочим , «NL» обозначает недетерминированный лог- класс класса сложности , который вообще не имеет смысла в той позиции, в которой он появился в оригинальной цитате.
источник
Для хорошего описания обозначений Big O (а также little-o и Theta) я рекомендую книгу MIT Введение в алгоритмы профессора Лизерсона.
источник