Является ли O (log n) правильным временем выполнения T (n) для этого?

#c #time

#c #время

Вопрос:

Вот оно:

 for(i=n;i >0; i=i/2)
    printf(“%i”,i);

Я все еще новичок в этом, и любая помощь будет высоко оценена. Спасибо!

1. Правильно. i уменьшается вдвое на каждой итерации, пока не достигнет 0, поэтому количество итераций равно log (n) . Если n изначально <= 0, оно немедленно завершится.

2. Неправильно. “%i” является нестандартным и приведет к ошибке компиляции в обычном компиляторе, поэтому для этого нет времени выполнения.

3. Чтобы уточнить, @MikeCAT жалуется на неправильные символы кавычек, используемые в сообщении, т. Е. “%i” . Это должно быть "%i" .

Ответ №1:

Как уже указывалось в комментариях. Вы правы насчет сложности этого фрагмента кода. Просто используйте " , а не smart quote ” . Как указано @John Bollinger ” , не является частью стандартного набора символов базового исходного кода C.

Что касается сложности проверки, вы можете проверить это самостоятельно с помощью базового использования журнала:

 #include <stdio.h>
#include <math.h>

double getLog2(double n) {  
    return log(n) / log(2);  
} 

int main() {
    int n = 32;
    int nIterations = 0;
    for (int i = n; i > 0; i /= 2) {
        printf("%in", i);
        nIterations  ;
    }

    printf("nIterations = %d, getLog2(%d) = %d", nIterations, n, getLog2(n));
}

Когда вы запустите это, вы сможете увидеть nIterations значение, равное log для основания 2 из N. Вот пример запуска с N=64 :

 src : $ gcc logncomplexity.c -lm
src : $ ./a.out 
64
32
16
8
4
2
1
nIterations = 7, getLog2(64) = 7

1. %i полностью соответствует стандарту as %d , и оба имеют одинаковое значение как printf директивы полей. Нет особой причины для изменения OP. Но им нужно использовать символы двойных кавычек ASCII ( " ), в отличие от «умных» кавычек, которые они представляют в вопросе. Последних нет в базовом исходном наборе символов C, и компилятор, который принимает их вообще, вряд ли распознает их как разделители для строковых литералов.

2. Большое спасибо за ваш комментарий, я не мог заметить, что это не a " . Я обновлю свой ответ