Порядок определения роста от Reynolds & Tymann

47

Я читаю книгу под названием « Принципы информатики» (2008) Карла Рейнольдса и Пола Тиманна (опубликована в «Схемах Шаума»).

Во второй главе представлены алгоритмы с примером последовательного поиска, который просто перебирает список имен и возвращает TRUE, если в списке найдено данное имя.

Автор продолжает (стр. 17):

Мы говорим, что «порядок роста» алгоритма последовательного поиска равен n. Обозначения для этого T (n). Мы также говорим, что алгоритм, порядок роста которого находится в некотором постоянном множителе T (n), имеет тета NL скажем. «Последовательный поиск имеет тета n». Размер проблемы n, длина списка, в котором выполняется поиск.

Мне действительно трудно это понять. Книга изобилует ошибками, поэтому я не уверен, что я что-то упустил или есть опечатка в параграфе выше. В общем английском я редко вижу, чтобы любое предложение заканчивалось на «... сказать».

Я очень смущен.

Что означает Т? Книга не объясняет. Это для времени или для тета?

Если «тета NL» означает «Последовательный поиск имеет тета n». Что означает L? «Линейный» или «длина»?

Я написал издателям с просьбой объяснить. Они сказали, что отправят мое сообщение авторам. Они не ответили. Я также пытался взглянуть на другие источники, но у меня все еще возникает мучительное чувство, что я что-то неправильно понимаю - поэтому не могу успокоиться, пока не расшифрую этот параграф.

Если у кого-то есть копия этой книги, и он понял этот пункт. Тогда я был бы признателен, если бы вы сообщили мне, если этот абзац точен, или объясните его другими словами. Благодарю.

JW.
источник
Временная сложность T (n) из Википедии : «Поскольку время выполнения алгоритма может варьироваться в зависимости от разных входных данных одинакового размера, обычно используется временная сложность алгоритма в наихудшем случае, обозначаемая как T (n), которая определяется как максимальное количество времени, затрачиваемое на любые входные данные размера n. Менее распространенным и обычно указывается явно, является мера сложности среднего случая. Сложности времени классифицируются по характеру функции T (n). Например, алгоритм с T (n) = O (n) называется алгоритмом линейного времени, а [...] "
Стефан
1
Я полагаю, что это эта книга, и, в дополнение к не звездному обзору, который я только что оставил, есть еще одна датированная сегодня, что, вероятно, не случайно!
Джейсон С
Такое использование слова похоже на наименее используемое определение: предполагать или предполагать. Думайте об этом как "... скажем так". Все еще не уверен, что предложение имеет смысл.
Роджер Крюгер

Ответы:

77

Абзац неверный. К сожалению, это похоже на то, что студент, который не понимает материала, написал бы в качестве ответа на упражнение. Такого рода глупости нет места в учебнике. Не делайте резких движений. Положи книгу. Отойди от книги.

T(n)

T(n)Tn

T(1)=kT(n)=T(n1)+lognfor n>1
TT(n)=blahTT

T(n)n

Это явно было искажено. Я думаю, что авторы намеревались написать что-то вроде:

T(n)nn

Но, пожалуйста, мы не говорим «имеет тета », так же как, если - это ваша запись для роста, вы бы не сказали «Джон имеет 180 см». Это просто неправильная форма слов. На самом деле мы говорим: «Время выполнения алгоритма - тета  (или тета  )». В частности, обратите внимание, что - это инструмент для обсуждения математических функций, а не алгоритмов. Тета не означает, что время выполнения - это нечто; скорее это то, что вы можете использовать, чтобы говорить о времени выполнения.ч ч н н ΘnhhnnΘ

Между прочим , «NL» обозначает недетерминированный лог- класс класса сложности , который вообще не имеет смысла в той позиции, в которой он появился в оригинальной цитате.

Дэвид Ричерби
источник
12
Первый абзац заставил меня улыбнуться, потому что это именно то, что скажет вам полиция информатики :-) (+1 тоже, это хороший ответ).
Юхо
3
Большое спасибо за ваше объяснение. Это действительно очень полезно, и теперь я чувствую, что понимаю это немного лучше (или, по крайней мере, не чувствую страха за то, что не понимаю этот абзац). Я могу расслабиться сейчас.
JW.
2

T

Для хорошего описания обозначений Big O (а также little-o и Theta) я рекомендую книгу MIT Введение в алгоритмы профессора Лизерсона.

Onotation

Tnotation

abelenky
источник
1
Не похоже, что они вообще пытаются объяснить большой О - они явно говорят о тэте.
Дэвид Ричерби
Текст профессора Лизерсона конкретно описывает Тету как более точную вариацию BigO. Я понимаю, что могут быть и другие определения тэты, но я знаком с тэтой, связанной с BigO.
abelenky
2
Я не думаю, что это то, что происходит. Вместо этого, я подозреваю, что это общая небрежность написания «T (n) = n» и предположения (не говоря об этом явно), что все сделают вывод, что T (n) относится к времени выполнения, и, в частности, к времени выполнения алгоритма, который они иметь в виду, а п относится к размеру ввода.
DW