Какова сложность алгоритмического времени, если точное ∛ (n ^ 2) - PullRequest
Новая
       6

Какова сложность алгоритмического времени, если точное ∛ (n ^ 2)

0 голосов
/ 11 декабря 2018

Я вычислил ответ, который будет n повышен до 2/3.Может ли кто-нибудь сказать мне, что в худшем случае Big O ()

1 Ответ

0 голосов
/ 11 декабря 2018

Является ли это наихудшим случаем или нет, это зависит от используемого вами алгоритма.

Но в целом, если у вас количество операций, равное n^(2/3), тогда сложность в терминах O-notation - это O(n^(2/3)).

Позвольте мне объяснить это более подробно (чтобы мы могли избавиться от «общего» слова и дать окончательный ответ).

Рассмотрим простой алгоритм, который находит конкретное число в массиве n элементов.

Если ваш алгоритм выглядит примерно так: 

find(arr, number) {
    boolean found = false;
    for(i = 0; i < arr.length; i++) {
        if(arr[i] == number) {
            found = true;         
        }
    }
    return found;
}

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

Теперь сравните и сопоставьте этот алгоритм со следующим: 

find(arr, number) {
    for(i = 0; i < arr.length; i++) {
        if(arr[i] == number) {
            return true;
        }
    }
    return false;
}

Теперь сложность времени зависит от ввода массива.(Если у вас есть массив с 10 ^ 8 элементами, и первый элемент совпадает с элементом, который вы ищете, то все готово, и вы можете мгновенно вернуться без итерации по всему массиву).Таким образом, сложность наихудшего случая здесь становится O(n), но лучшим вариантом здесь является O(1).

Так что в основном все зависит от вашего алгоритма, как он работает.Я предполагаю, что ваше намерение, когда вы говорите «точный», заключается в том, что у вас есть первая версия find, которую я описал выше.И если это так, то да, сложность времени наихудшего случая составляет O(n^2/3)

...