Какова среда выполнения этого кода в тета-нотации? - PullRequest
Новая
       28

Какова среда выполнения этого кода в тета-нотации?

0 голосов
/ 23 октября 2018

Я считаю, что время выполнения func2 - O (n * log (n)).
Но некоторые люди говорили мне, что это не так. 

int func2(int* arr, int n){
    int i, j;

    for (i = 1; i <= n; i *= 2)
        reverseArray(arr, i);
    }
}

void reverseArray(int* arr, int n){
    int left, right, temp;

    for (left = 0, right = n-1; left <= right; left++, right--){
        temp = arr[left];
        arr[left] = arr[right];
        arr[left] = temp;
    }
}

1 Ответ

0 голосов
/ 23 октября 2018

func2 выполняется за линейное время, т. Е. O(n)

Объяснение:

Легко сказать, что временная сложность метода reverseArray линейна, т. Е. big-Theta(n)

давайте предположим, что func2 вызывается с n = 8;

Вызовами reverseArray будут: - 

reverseArray(arr, 1)
reverseArray(arr, 2)
reverseArray(arr, 4)
reverseArray(arr, 8)

Таким образом, общее время выполнения = 1 + 2 + 4 + 8 =15, то есть 2 * 8 - 1

Так, если бы n было степенью 2, общее время выполнения = O(2*n - 1)

Если бы n не было степенью 2, общее время работы было быbe = O(2*K - 1), где K - наивысшая степень 2, меньшая n.Мы можем с уверенностью сказать, O(2*K - 1) = O(2*n - 1) [поскольку, O является верхней границей]

O(2*n - 1) = O(n)

Для тета-записи нижняя граница равна O(2*K - 1), где K - наивысшая степень 2 меньшечем н.Следовательно, сложность времени = Theta(2^(floor(log(n)base2)+1))

...