Сложность времени printf()?

Question

Я хотел бы определить время сложность Printf, такие как:

{ 
    printf("%d", 
      i); 
} 

Или:

{ 
    printf("%c", 
      array[i]); 
} 

Правильно ли считать, что время сложность Printf всегда O (1) или не?

[EDIT] Давайте функцию, которая свопы два значения: затраты экспрессии

void swap(...) 

{ 

     tmp = x; 
     x = y;  
     y = tmp; 

} 

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

void swap(...) 

{ 

     tmp = x; 
     x = y;  
     y = tmp; 

     printf("Value of x: %d", x); 
     printf("Value of y: %d", y); 

} 

Могу ли я сказать, что T (n) все еще O (1) в этом случае?

Answer 1

Это странно, чтобы попытаться оценить временную сложность printf(), как это блокирование операции ввода/вывода, который выполняет обработку какой-нибудь текст и выполняет операцию записи с помощью серии write() системных вызовов через промежуточный буферный слой.

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

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

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

Также ваш код предполагает, что выход возникает только для фактического тестирования функциональности и не должен рассматриваться как часть вычисления вообще. Лучший способ - переместить ввод/вывод из функций, которые вы хотите рассмотреть, для целей сложности, например. к функции main(), чтобы подчеркнуть, что вход и выход есть только для проверки кода.

Осуществление O (1) функции замены без ввода/вывода:

void swap(int *a, int *b) 
{ 
    int tmp = *a; 
    *a = *b; 
    *b = tmp; 
} 

Альтернативная реализация без временной переменной (только для развлечения):

void swap(int *a, int *b) 
{ 
    *a ^= *b; 
    *b ^= *a; 
    *a ^= *b; 
} 

Реализация основной функции:

int main(int argc, char **argv) 
{ 
    int a = 3, b = 5; 

    printf("a = %d; b = %d\n", a, b); 
    swap(&a, &b); 
    printf("a = %d; b = %d\n", a, b); 

    return 0; 
} 

Answer 2

Временная сложность означает не то, сколько времени требуется для выполнения конкретной программы. Сложность времени измеряется в количестве частот, которые она требует для запуска. Теперь, если вы рассматриваете простую инструкцию printf(), то, очевидно, временной сложностью будет O (1).

См: Time Complexity For Algorithm

Answer 3

Я не думаю, что это действительно разумный вопрос, чтобы спросить, потому что поведение printf «s в основном определяется реализацией. C не накладывает никаких ограничений на то, что система решает сделать, как только он достигнет printf. У этого есть понятие потока . В разделе 7.21 стандарта C11 указывается, что printf действует над потоком.

C позволяет реализацию делать все, что он хочет с потоками после того как они записаны (7.21.2.2):

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

Таким образом, ваш призыв к printf разрешается выписывать 1 Тб каждый раз, когда char печатается, и 1 байт, когда печатается int.

Стандарт не требует даже, что запись происходит, когда printf на самом деле называется (7.21.3.3):

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

И the standard doesn't specify whether stdout is buffered or unbuffered.Таким образом, C позволяет printf делать практически все, что бы вы ни пожелали, как только вы попросите его написать.

Answer 4

В целом сложность printf() - это O (N) с N количество символов, которые выводятся. И эта сумма не обязательно является малая константа, так как в этих двух вызовов:

printf("%s", myString); 
printf("%*d", width, num); 

Длина myString не обязательно иметь верхнюю границу, поэтому сложность первого вызова представляет собой О (strlen(myString)), а второй вызов выдаст width символов, от которых можно ожидать времени O (width).

Однако в большинстве случаев объем вывода, записанный printf(), будет ограничен небольшой константой: строки формата обычно представляют собой константы времени компиляции, а вычисленные поля ширины, как указано выше, редко используются. Строковые аргументы более часты, но часто позволяют давать и верхний предел (например, когда вы выводите строку из списка сообщений об ошибках). Итак, я бы сделал ставку, что по крайней мере 90% реальных звонков printf() - это O (1).