2

Подскажите, пожалуйста, с какой скоростью будет работать этот алгоритм? Алгоритм считает суммы предшествующих элементов массива. Справедлива ли для этого алгоритма оценка O(n)? Псевдокод:

Функ(A[...], n)    {A - массив, нумерация начинается с 1, n - длина массива}   
    i <- 2    
    Пока i <= n: {Начало цикла 1}
        A[i] <- A[i] + A[i-1]
        i <- i + 1
    {Конец цикла 1}

C++:

void funk1(int *mass, int len){
    for (int i = 1; i < len; i++) {
        mass[i] += mass[i - 1];
    }
}

1 ответ 1

2

Давайте разберём.

За каждую итерацию цикла выполняется 7 операций: вычитание единицы, два индексирования, два чтения, одно сложение и одна запись. Расход на управление циклом — одна проверка и одно увеличение счётчика на итерацию, ну ещё один переход. Итого 10 операций на итерацию.

Сколько всего итераций? Очевидно, n - 1 (или len - 1 в вашей C++-записи). Плюс ещё операция на инициализацию переменной. Итого 10 * n - 10 + 1 = 10 * n - 9.

Является ли 10 * n - 9 O(n), вы должны знать сами.


Да, я знаю, что подсчёт не вполне корректен, т. к. оптимизатор может вмешаться и улучшить код, сложения могут стоить дороже, разные операции отображаются на разное число циклов процессора и т. д. Но это повлияет лишь на коэффициент при n.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.