Временная сложность первичных инструкций в Си

Question

У меня есть вопрос об алгоритмической сложности.

Имеют ли базовые инструкции в C эквивалентную сложность, если нет, то в каком порядке они находятся: если записать / прочитать одну ячейку матрицы,+ b, a * b, a = b ...

Спасибо

Answer 1

Сложность равна , а не времени, которое требуется для выполнения «базовых» строк кода, таких как сложение, умножение, деление и т. Д.

Даже если эти выражения имеют разное время выполнения, все ониимеют сложность O (1).

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

Например, -если вы пишете код, который должен найти наибольшее значение в массиве целых чисел, время выполнения зависит от количества элементов в массиве.Код должен будет посетить каждый элемент массива, чтобы проверить, больше ли он, чем предыдущие элементы.Следовательно, сложность составляет O (N), где N - количество элементов.Исходя из этого, мы не можем сказать, сколько времени потребуется, чтобы найти самый большой элемент, но мы можем сказать, что для массива из 1000 элементов потребуется в 10 раз больше времени, чем для массива из 100 элементов.

Теперьесли бы вы сделали то же самое со связанным списком (то есть нашли самый большой элемент), сложность снова была бы O (N).Однако это не говорит о том, что связанный список работает так же, как массив.Это только говорит о том, что он масштабируется так же, как и массив.

Упрощенный способ сказать это - если нет задействованных циклов, сложность всегда равна O (1).

Answer 2

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

Я думаю, вы ищете информацию о циклах на инструкцию .

* 1006.* Однако даже это не вся история.Современные процессоры имеют иерархические кэши.Если ваш алгоритм работает с данными, которые в основном находятся в быстром кеше, он будет работать на намного быстрее, чем программа, которая работает с данными, к которым необходимо многократно обращаться из ОЗУ, жесткого диска или по сети.Количество вычислений, выполненных на нагрузку, составляет арифметическая интенсивность приложения . Модели Roofline предоставляют инструмент для размышлений об этом.Вы можете добиться лучшего использования кэша с помощью блокирования и других методов , хотя в подполе алгоритмы избегания связи подробно рассматривается это.

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