О сложности времени / пространства в стандартах C/C++

Question

Недавно я прочитал кое-что об абстрактной машине и правиле "как будто" ( что такое правило "как будто"?) И требованиях к временной сложности стандартной библиотеки (например, такой: действительно ли list::size() O (n)?).

1. Являются ли требования к пространственно-временной сложности стандартной библиотеки с точки зрения абстрактной машины или реальной конкретной машины?

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

2. Упоминали ли стандарты что-либо о сложности времени / пространства для кода нестандартной библиотеки?

например, я могу написать собственный код сортировки и ожидать O(n log n) времени, но если реализация просто обрабатывает это как код в абстрактной машине, то разрешается генерировать более медленную сортировку в сборке и машинном коде, например, изменить ее на O(n^2) сортировать, даже если в реальной ситуации это вряд ли удастся.

Или, может быть, я что-то упустил из-за требований трансформации между абстрактной машиной и реальной конкретной машиной. Можете ли вы помочь мне уточнить?:)

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

Answer 1

1. Являются ли требования к пространственно-временной сложности стандартной библиотеки с точки зрения абстрактной машины или реальной конкретной машины?

Требования к сложности с точки зрения абстрактной машины:

[intro.abstract] Семантические описания в этом документе определяют параметризованную недетерминированную абстрактную машину...

---

2. Упоминали ли стандарты что-либо о сложности времени / пространства для кода нестандартной библиотеки?

Нет. Единственные требования сложности в стандарте касаются стандартных контейнеров и алгоритмов.

если реализация просто обрабатывает это как код в абстрактной машине, ей разрешается генерировать более медленную сортировку в ассемблере и машинном коде, например, изменить ее на O(n^2) sort

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

Answer 2

Многие требования к сложности в стандарте C++ связаны с определенным количеством конкретных операций. Это ограничивает реализацию.

Например std::find_if

В большинстве last - first приложения предиката.

Это более конкретно, чем " O (N), где N = std::distance(first, last) ", поскольку он указывает постоянный коэффициент 1.

И есть другие, которые имеют границы Big-O, определяющие, какие операции считаются

Например std::sort

O (N · log (N)), где N = std::distance(first, last) сравнения.

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

Answer 3

Как вам сказали в комментариях, стандарты не предъявляют никаких требований относительно сложности времени или пространства. И что касается вашего дополнительного неявного вопроса, да, компилятор может изменить ваш код O(n log n) для запуска за O(n²) времени. Или в O(n!), Если захочет.

Основное объяснение состоит в том, что стандарт определяет правильные программы, и программа является правильной независимо от того, сколько времени требуется для выполнения или сколько памяти она использует. Эти детали оставлены для реализации.

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

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

TL; DR: плохая производительность (сложность времени, сложность памяти и т. Д.) Не влияет на соответствие, но заставит вас искать новый компилятор.