Есть ли какое-либо непротиворечивое определение сложности времени для языков реального мира, таких как C ++?

Question

C ++ пытается использовать концепцию временной сложности в спецификации многих библиотечных функций, но асимптотическая сложность - это математическая конструкция, основанная на асимптотическом поведении, когда размер входных данных и значения чисел стремятся к бесконечности.

Очевидно, что размер скаляров в любой конкретной реализации C ++ конечен.

Какова официальная формализация сложности в C ++, совместимая с конечным и ограниченным характером операций C ++ ?

Примечание: само собой разумеется, что для контейнера илиВ алгоритме, основанном на параметре типа (как в STL), сложность может быть выражена только через количество предоставленных пользователем операций (скажем, сравнение для отсортированного материала), а не через элементарные операции языка C ++. Это не проблема здесь.

РЕДАКТИРОВАТЬ:

Стандартная цитата:

4.6 Выполнение программы [intro.execution]

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

2 Некоторые аспекты и операции абстрактной машины описаны в этом международном стандарте как определяемые реализацией (например,, sizeof(int)). Они составляют параметры абстрактной машины. [...]

Язык C ++ определяется в терминах абстрактной машины на основе скалярных типов, таких как целочисленные типы с конечным числом,определенное количество бит и только так много возможных значений. (Dito для указателей.)

Не существует "абстрактного" C ++, где целые числа были бы неограниченными и могли бы "стремиться к бесконечности".

Это означает, что в абстрактной машине любой массив, любой контейнер, любая структура данных ограничены (даже если возможно огромны по сравнению с доступными компьютерами и их крошечной памятью (по сравнению, например, с 64-битным числом).

Answer 1

Очевидно, что размер скаляров в любой конкретной реализации C ++ конечен.

Конечно, вы правы с этим утверждением! Другой способ сказать, что это так: «C ++ работает на оборудовании, а оборудование конечно». Опять же, абсолютно правильно.

Однако ключевой момент таков: C ++ не формализован для какого-либо конкретного оборудования. Вместо этого он формализован для абстрактной машины .

Например, sizeof(int) <= 4 верно для всего оборудования, для которого я лично когда-либо программировал. Однако в стандарте вообще нет верхней границы, касающейся sizeof(int). Что в стандарте C ++ указано значение типа int, long?

Итак, на определенном оборудовании вход для некоторой функции void f(int) действительноограничено 2^31 - 1. Таким образом, теоретически можно утверждать, что, независимо от того, что он делает, это алгоритм O (1), потому что его число операций никогда не может превышать определенный предел (который является определением O (1)). Однако на абстрактной машине буквально такого ограничения нет, поэтому этот аргумент не может быть сохранен.

Итак, в целом, я думаю, что ответ на ваш вопрос заключается в том, что C ++ не так ограниченкак Вы думаете. C ++ не является ни конечным, ни ограниченным. Оборудование есть. C ++ абстрактной машины нет. Следовательно, имеет смысл заявить о формальной сложности (как определено математикой и теоретической CS) стандартных алгоритмов.

Утверждение, что каждый алгоритм является O (1), просто потому, что на практике всегда существуют аппаратные ограничения, может быть оправдано чисто теоретическим мышлением, но это было бы бессмысленно. Хотя, строго говоря, большой О имеет смысл только в теории (где мы можем идти к бесконечности), на практике он обычно оказывается весьма значимым, даже если мы не можем идти к бесконечности, а только к 2^32 - 1.

ОБНОВЛЕНИЕ:

Относительно вашего редактирования: Вы, кажется, перепутали две вещи:

1. Не существует конкретной машины (будь то абстрактная илинастоящий) имеет тип int, который может «стремиться к бесконечности». Это то, что вы говорите, и это правда! Таким образом, в этом смысле всегда есть верхняя граница.
2. Стандарт C ++ написан для любой машины, которая когда-либо может быть изобретена в будущем. Если кто-то создает оборудование с sizeof(int) == 1000000, это нормально для стандарта. Итак, в этом смысле верхней границы нет.

Надеюсь, вы понимаете разницу между 1. и 2. и почему оба они являются действительными утверждениями и не противоречат друг другу. Каждая машина конечна, но возможности поставщиков оборудования бесконечны.

Таким образом, если стандарт определяет сложность алгоритма, он делает (должен делать) это с точки зрения пункта 2. В противном случае он ограничил бырост оборудования. И этому росту нет предела, поэтому имеет смысл использовать математическое определение сложности, которое также предполагает отсутствие ограничений.

Answer 2

Асимптотическая сложность - это математическая конструкция, основанная на асимптотическом поведении, когда размер входов и значения чисел стремятся к бесконечности.

Правильно. Точно так же алгоритмы являются абстрактными объектами, которые можно анализировать в отношении этих метрик в рамках данной вычислительной структуры (такой как машина Тьюринга).

C ++ пытается использовать концепцию сложности времени в спецификации многих библиотекfunctions

Эти спецификации сложности накладывают ограничения на алгоритм, который вы можете использовать. Если std::upper_bound имеет логарифмическую сложность, вы не можете использовать линейный поиск в качестве основного алгоритма, потому что он имеет только линейную сложность.

Очевидно, что размер скаляров в любой данной реализации C ++ конечен.

Очевидно, что любой вычислительный ресурс конечен. Ваша RAM и CPU имеют только конечное число состояний. Но это не означает, что все является постоянным временем (или что проблема остановки решена ).

Это вполне разумно и работоспособно для стандарта, определяющего, какие алгоритмы реализация может использовать (std::map, реализуемая как красно-черное дерево, в большинстве случаев является прямым следствием требований сложности его интерфейсных функций). Последствия для фактического исполнения «физического времени» реальных программ не являются ни очевидными, ни прямыми, но это не входит в сферу.

---

Позвольте мне изложить это в простом процессе, чтобы указать на несоответствиев вашем аргументе:

1. Стандарт C ++ определяет сложность для некоторой операции (например, .empty() или .push_back(...)).

2. Разработчики должнывыберите (абстрактный, математический) алгоритм, который удовлетворяет этому критерию сложности.

3. Разработчики затем пишут код, который реализует этот алгоритм на некотором конкретном оборудовании .

4. Люди пишут и запускают другие программы на C ++, использующие эту операцию.

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

Эти эффекты и свойства не указаны явно в стандарте (даже если они являются причиной для этих конкретных стандартных условий). Вот как работают технические стандарты: вы описываете, как все должно быть сделано, а не почему это выгодно или как его лучше всего использовать.

Answer 3

Вычислительная сложность и асимптотическая сложность - это два разных термина. Цитирование из Википедии :

Сложность вычислений или просто сложность алгоритма - это количество ресурсов, необходимых для его запуска .

Для сложность времени количество ресурсов преобразуется в количество операций :

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

В моем понимании, это концепция, которую использует C ++, то есть сложность оценивается с точки зрения числа операций . Например, если количество операций, выполняемых функцией, не зависит от какого-либо параметра, то оно является постоянным.

Наоборот, асимптотическая сложность - это нечто иное:

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

Асимптотическая сложность полезна для теоретического анализа алгоритмов.

Answer 4

Какова официальная формализация сложности в C ++, совместимая с конечным и ограниченным характером операций C ++?

Нет ни одного.