Временная сложность алгоритма троичного поиска

Question

У меня есть задание, которое хочет, чтобы я написал троичный алгоритм поиска и впоследствии вычислил его временную сложность. Я смог написать алгоритм для него, но не смог придумать идеи, как вычислить его сложность. Я думаю, что не понял концепцию бета-тета-нотации.

Вот мой код: он работает как бинарный поиск, но только делит список на части и продолжает поиск таким образом.

    *some list which contains n increasingly-ordered integers;*

    int num;

    int min = 1;
    int max = n;

    int middle1 = (2*min+max)/3; 
    int middle2 = (min+2*max)/3;

    cin >> num;    //num is the number that is wanted to be found

    while (middle1 != middle2)
    {
        middle1 = (2*min+max)/3;
        middle2 = (min+2*max)/3;

        if(num <= list[middle1])
            max = middle1;
        else if(num >list[middle1] && num <= list[middle2])
            {
                    min= middle1; 
                    max = middle2;
            }
        else
            min = middle2;
    }
    if(num == list[max])
        cout << "your number is found in the "<< max <<"th location\n";
    else
        cout << "number cannot be found";

Если бы вы могли объяснить, как определить его сложность в терминах бета-тета-нотации, это было бы очень полезно для меня.

Answer 1

На каждом шаге вы уменьшаете размер диапазона поиска на постоянный коэффициент (в данном случае 3).Если вы найдете свой элемент после n шагов, то диапазон поиска будет иметь размер N = 3 ⁿ .И наоборот, количество шагов, которое вам нужно, пока вы не найдете элемент, является логарифмом размера коллекции.То есть время выполнения равно O (log N ).Немного дальнейших размышлений показывает, что вы также можете всегда создавать ситуации, в которых вам нужны все эти шаги, поэтому наихудшее время выполнения на самом деле - Θ (log N ).

Answer 2

Это & Theta; (log3 (N)). Чтобы проверить, как рассчитать сложность, просто отметьте http://en.wikipedia.org/wiki/Big_O_notation

Чтобы узнать больше о троичном поиске, просто зайдите также на страницу википедии: http://en.wikipedia.org/wiki/Ternary_search