Какова временная сложность этого алгоритма в виде нотации Big-O?

Question

Это алгоритм для этого вопроса: повернуть массив из n элементов, оставленных позициями i.Например, при n = 8 и i = 3 массив abcdefg поворачивается в defghabc.

/* Alg 1: Rotate by reversal */

void reverse(int i, int j)
{   int t;
    while (i < j) {
        t = x[i]; x[i] = x[j]; x[j] = t;
        i++;
        j--;
    }
}

void revrot(int rotdist, int n)
{   reverse(0, rotdist-1);
    reverse(rotdist, n-1);
    reverse(0, n-1);
}

Какова временная сложность этого метода?И есть ли лучшее решение этой проблемы?Спасибо, действительно.

Answer 1

Согласен, это будет O (n), так как мы просто сдвигаемся.

В качестве пищи для размышлений другой возможный алгоритм - создать новый массив с добавленным к нему оригиналом (т. Е. Abcd -> abcdabcd). Затем сдвиньте указатели прямо n раз! Конечно, вам понадобятся два указателя, один для конца, другой для начала. Не забудьте отрезать конец с помощью '\ 0'

То же время выполнения между прочим.

Answer 2

Цикл должен идти не более (i + j) / 2 раза. Отбрасывание константы, O (i + j).

Answer 3

Big-O обозначение:

n всегда O (n). (циклы, поскольку они должны пройти несколько итераций)

1, т. O (1). (если выписка, указанное количество)

Answer 4

Должно быть приблизительно линейным O(n).