Как обычно, читая вещи, я понял этот вопрос. Если у меня есть инициализация массива символов, как показано ниже, какова будет временная сложность для этого оператора?Какова временная сложность инициализации массива символов?
char array[] = {'a','b','c','d','e'};
Будет ли он фактически выполнять 5 раз для назначения каждой переменной; как мы делаем в цикле. Если предположение верно, почему это так?
В зависимости от того, где происходит объявление и интеллекта компилятора, это может быть O (1) или O (n). в некоторых случаях:
Для 2., я думаю, должно быть больше, чем что. Также необходимо, чтобы компилятор смог доказать, что никогда не было сравнения базового адреса массива. Два экземпляра одного и того же массива, например, из разных рекурсивных вызовов, всегда должны быть разными. Единственный случай, когда я знаю, где такое сгибание разрешено, - это «сложные» литературные составные литералы. –
@JensGustedt без 'const', это, возможно, необходимо. но настоящий интеллектуальный компилятор может рассматривать его так, как будто он объявлен 'const', независимо от того, объявлено оно так или нет. – LeleDumbo
Даже с 'const', для двух объектов, которые отличаются проверкой с' == 'для своих адресов, нужно возвращать' false'. Это требование выполняет два экземпляра одной и той же переменной, которые соответствуют двум различным рекурсивным вызовам. –
Это O (N). Это может быть быстрый или эффективный O (N). И если это статически выделенный массив, инициализация будет выполняться только один раз.
Но в любом случае это O (N).
Обратите внимание, что даже если это массив, который помещается в двоичное изображение программы (поскольку компилятор определяет, что массив никогда не изменяется), это все еще операция O (N) для инициализации, хотя инициализация может происходят до того, как событие программы достигнет main() или сделано как часть загрузки изображения программы.
Это O (N), потому что независимо от того, что инициализация должна записывать в каждое местоположение массива, поэтому массив, который в 100 раз длиннее другого, будет иметь порядок в 100 раз больше операций, выполняемых для завершения инициализации ,
Я не понимаю. Насколько я знаю, значения такой статической инициализации помещаются в двоичное изображение. Обычно эта часть двоичного файла тогда «mmap» (или аналогичная) с «копией при записи». Накладные расходы на инициализацию тогда возникают только тогда, когда значение записывается в определенное место. В частности, переменная, которая никогда не имеет доступа, вообще не имеет накладных расходов. В терминах обозначения BigO общая стоимость - «O (M)», где «M» - это номер для доступа к отдельным местоположениям массива. Так что с точки зрения bigO нет накладных расходов вообще. Однако константа, спрятанная в bigO, является страницей. –
Как и другие, это можно сделать в O (n) времени.
Но это никогда не может быть O (1) !! Как вы можете писать в n ячейках памяти (независимо от того, какой тип памяти мы имеем) за меньшее время? O (1) означает, что операция не зависит от размера входа. Я не хочу приводить в дискуссию машины для обучения, но где-то во время выполнения всегда будет операция O (n) с вышеуказанным оператором.
Нет, этот анализ слишком грубый. Вы должны измерить его в «M» количество раз, когда программа доступа к элементу массива получает доступ. См. Мой комментарий для ответа Мишеля Берра. –
@User - Вы можете написать сразу несколько символов, особенно если строка коротка. На моей 64-битной машине компилятор перемещает 8 символов за один раз с использованием одного регистра. –
@BoPersson да, но количество символов, которые вы можете перемещать сразу, ограничено. – UmNyobe
Сложность времени будет равна 0. Не O или o (n). Место для массива будет установлено с начальными значениями ДО ПРОГРАММЫ ПРОГРАММЫ. Место и значения будут подготовлены на стадии компиляции и настроены на этап компоновки.
Не будет никаких команд для реализации указанной линии. И НЕТ времени.
Я бы предположил, что любой неидиотский компилятор выполнит его в 'O (n)' с не более чем 5 назначениями в 5 разных мест памяти. (и, возможно, меньше, если он решит векторизовать) – Mysticial
Если массив такой же, как в вашем примере, компилятор просто поместил бы значения массива в виде последовательного фрагмента памяти в сегменте данных приложений, и пусть 'array' указывает на это. Никакой инициализации или цикла вообще. –
@Joachim: нет, если 'array' находится в стеке, он должен быть инициализирован локально тогда.(Но в стандарте нет ничего, что говорило бы о том, как компилятор должен это сделать, поэтому вопрос не отвечает в ответ - проверьте вывод компилятора. GCC делает 5 байтов здесь.) – Mat