Временная сложность этого алгоритма с шагами по его определению в основном для строки 4

Question

void programB(int n) {
    long prod = 1;
    for (int c=1;c<n;c=c*3)
        prod = prod * c;

Я не знаю, как рассчитать сложность времени для 3-й строки кода. Это п ^ 3?

Answer 1

Если бы у вас было

void programB(int n) {
    long prod = 1;
    for (int c=1;c<=n;c=c+1)
        prod = prod * c;

это будет проходить через n вещи, так что будьте O (n).

С

void programB(int n) {
    long prod = 1;
    for (int c=1;c<=n;c=c+1)
        for (int c=1;c<=n;c=c+1)
            prod = prod * c;

это проходит через n вещи для каждой из n вещей, давая вам O (n ^ 2)

Чтобы получить n ^ 3, вам нужен еще один цикл for:

void programB(int n) {
    long prod = 1;
    for (int c=1;c<=n;c=c+1)
        for (int c=1;c<=n;c=c+1)
            for (int c=1;c<=n;c=c+1)
                prod = prod * c;

Ваш кейс не выполняет все действия n, так как он скачет с шагом c=c*3), давая силы три, как показано в ответе Кабануса: 1, 3, 9, 27 ... Это дает вам log_3 n или O (log (n)) - поскольку база не имеет значения.

Answer 2

Временная сложность этого цикла for составляет log n base a

int n,a;
    for(int c=1;c<n;c=c*a) 
    {
          //Some code
    }

Answer 3

Если вы не участвуете в тесте и у вас есть роскошь времени, я всегда советую попробовать несколько цифр:

n=10:
c = 1, 3, 9

n=20:
c = 1,3,9

n=30:
c=1,3,9,27

Как видите, число итераций не только не меньше n^3, но и намного меньше n. В основном вы проверяете, сколько раз вы можете умножить 3 в пределах n в этом цикле, что является моей подсказкой.