Big-O Сложность двух проблем - PullRequest
Новая
       8

Big-O Сложность двух проблем

1 голос
/ 10 апреля 2020

Я практиковал несколько проблем сложности Big-O для одного из моих классов, и эти две проблемы, кажется, ставят меня в тупик.

Для обоих из них мне нужно определить лучший и худший случаи. сложность.

Q1 

function FUNC3(int array[n], int n, int key)
    int i = 1;
    while (i < n) do {
        if (key == array[0]) then
            i = i + n^0.25;
        else
            i = i + n^0.5;
    }

Лучший случай, который я получил, был: O (n / n ^ 0.5), в то время как мой худший случай был: O (n / n ^ 0.25)

Q2 

function FUNC4(int array[n], int n, int key)
    for (int i=1; i<n; i = i * 2) do
        for (int j=0; j<sqrt(n); j++) do {
            if(array[0] == key) then {
                int k = 1;
                while (k < n) do
                    k = k * sqrt(n);
            }
        }

Для этого я получил лучший случай: O (logn x sqrt (n)), с наихудшим случаем: O (logn xn)

Хотя я не очень уверен в этих ответах, все ли выглядят правильно?

1 Ответ

0 голосов
/ 10 апреля 2020

Давайте рассмотрим каждый из них в отдельности. Вот ваша первая функция: 

function FUNC3(int array[n], int n, int key)
    int i = 1;
    while (i < n) do {
        if (key == array[0]) then
            i = i + n^0.25;
        else
            i = i + n^0.5;
    }

Вы правы, что наилучшее время выполнения равно Θ (n / n 0.5 ), а худшее - case (n / n 0,25 ). Это может помочь переписать их, упрощая показатели; первое время выполнения:

Θ (n / n 0.5 ) = Θ (n 0.5 ) = Θ (√n)

, а второе время выполнения -

Θ (n / n 0.25 ) = Θ (n 3/4 ​​).

Теперь давайте посмотрим на вторую функцию: 

function FUNC4(int array[n], int n, int key)
    for (int i=1; i<n; i = i * 2) do
        for (int j=0; j<sqrt(n); j++) do {
            if(array[0] == key) then {
                int k = 1;
                while (k < n) do
                    k = k * sqrt(n);
            }
        }

Чтобы определить время выполнения, давайте используем проверенный временем принцип

"Если сомневаетесь, работайте внутри out! "

Начнем с самого внутреннего l oop: 

int k = 1;
while (k < n) do
    k = k * sqrt(n);

Этот l oop подлый - он никогда не запускается более трех раз, потому что значения k будет 1, затем √n, затем n. Это означает, что l oop выполняет O (1) общей работы. В результате мы можем переписать весь код как 

function FUNC4(int array[n], int n, int key)
    for (int i=1; i<n; i = i * 2) do
        for (int j=0; j<sqrt(n); j++) do {
            if(array[0] == key) then {
                do O(1) work;
            }
        }

Поскольку оператор if выполняет O (1), независимо от того, выполняется ли он, у нас остается 

function FUNC4(int array[n], int n, int key)
    for (int i=1; i<n; i = i * 2) do
        for (int j=0; j<sqrt(n); j++) do {
            do O(1) work;
        }

Если мы выполняем O (1) работу √n раз, то время выполнения равно Θ (√n), поэтому внутренняя l oop становится 

function FUNC4(int array[n], int n, int key)
    for (int i=1; i<n; i = i * 2) do
        do sqrt(n) work

, поскольку работа, выполненная во внутренней l oop не зависит от значения i, работа, проделанная здесь, является просто произведением числа внешних l oop итераций и работы, выполненной за одну итерацию. Внешний l oop выполняется Θ (log n) раз, поэтому работа здесь Θ (√n log n), независимо от содержимого массива. Таким образом, время выполнения в лучшем и худшем случаях для функции одинаково, поскольку общая выполненная работа (асимптотически) всегда одинакова.

Надеюсь, это поможет!

...