Почему предполагается, что временная сложность умножения на n постоянна?

Независимо от того, как реализована операция умножения (или деления) (т.е. является ли это программной функцией или аппаратной инструкцией), она не будет решена во времени O(1). при больших значениях n процессор не может даже вычислить его по одной инструкции.

Почему в таких алгоритмах эти операции постоянны и не зависят от n?

for (i = 1; i <= n; i++) {
    j = n;
    while (j > 1)
        j = j / 3;    //constant operation
}

Как это будет реализовано, зависит от базовой архитектуры. В большинстве практических случаев это не имеет значения и может быть ограничено достаточно большой константой. Фактически, константа может быть максимально возможным значением, и в этом случае операция немедленно ограничивается. В любом случае, это обычно не имеет отношения к анализируемому алгоритму и только искажает то, что нас действительно интересует.

Zabuzard 29.10.2018 21:14

Обычно умножение собственных типов составляет O (1) (постоянное время). Типы больших целых чисел, такие как используемые в Java, .NET и других средах, обычно имеют более высокую сложность. См., Например, javaspecialists.eu/archive/Issue236.html.

Jim Mischel 29.10.2018 21:17

@JimMischel, мы вычисляем сложность для больших n значений. поэтому мы должны позволить n быть как можно большим. тогда почему умножение на n постоянное? (насколько я знаю, обычно считается постоянным)

Mehran Ghofrani 29.10.2018 21:26

Просто примите это как предположение (иногда принимаемое), показывающее разрыв между теорией и практикой. С теоретической точки зрения вы также можете подвергнуть сомнению постоянную сложность сложения, учитывая физику: скорость света и верхний предел плотности информации на площадь / объем (до того, как все потеряно в черной дыре).

sascha 29.10.2018 21:44

Пожалуйста, перечитайте мой комментарий. Если ваш n является собственным типом (например, long или double), то значение не имеет значения. Система может умножать на 9324568078 так же быстро, как и на 7. Если n какой-то другой, неродной тип (например, BigInteger), то умножение имеет более высокую сложность, как описано в статье, на которую я ссылался.

Jim Mischel 29.10.2018 22:54

Умножение произвольной точности за один шаг машины - это физически нереалистичная лазейка, которая добавляет удивительное количество мощности машине, которая, как предполагается, имеет это - см. cs.stackexchange.com/questions/76797/…. Мелкий шрифт большинства теоретических машин запрещает это, обычно говоря, что нельзя предполагать, что числа становятся слишком большими, или не обеспечивает умножение, которого достаточно, чтобы числа оставались в разумном диапазоне.

mcdowella 30.10.2018 06:49
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
6
679
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Сложность времени - это не мера времени. Это мера «основных операций», которую можно определить по своему усмотрению. Часто любая арифметическая операция считается базовой. Иногда (например, при рассмотрении временной сложности алгоритмов сортировки или операций с хеш-таблицами) основными операциями являются сравнения. Иногда «базовые операции» - это операции с отдельными битами (в этом случае j=j/3 будет иметь временную сложность O (log (j)).

Как правило, соблюдаются следующие правила:

  • если вы говорите о сортировке или хэш-таблицах, основные операции - это сравнения
  • если вы говорите о любом другом практическом алгоритме, основные операции - это арифметические операции и присваивания.
  • если вы говорите о классах P / NP, основные операции - это количество шагов детерминированной машины Тьюринга. (У считать это эквивалентно битовым операциям).
  • Если вы, как эксперт по теории сложности, говорите о практических алгоритмах, вы часто предполагаете, что базовые типы имеют ~ log n битов, а основные операции - это арифметические операции и присваивания этим ~ log n битовым словам.

Другие вопросы по теме