Время выполнения бинарного поиска со сравнением - PullRequest
Новая
       6

Время выполнения бинарного поиска со сравнением

1 голос
/ 29 февраля 2020

У меня есть этот код: 

public static int compare(String s1, String s2) {
    int n = Math.min(s1.length(), s2.length());
    for (int i = 0; i < n; i++) {
        char c1 = s1.charAt(i);
        char c2 = s2.charAt(i);
        int diff = c1 - c2;
        if (diff != 0) {
            return diff; 
        }
    }
    return s1.length() - s2.length();
}

public static boolean exists(String word, String[] dict) {
    int left = 0;
    int right = dict.length-1;
    while (left <= right) {
        int middle = (left + right) / 2;
        int comparison = compare(dict[middle], word); 
        if (comparison < 0) {
            left = middle+1;
        } 
        else if (comparison > 0) {
            right = middle-1;
        } else {
            return true;
        } 
    }
    return false; 
}

Мне нужно вычислить сложность существующей функции.
Я сказал, что это O (K * logN), а N - это количество элементов в массив, а K - количество букв в слове.
Ответ O (logN), значит, я не должен был включать compare сложность функции в мои вычисления?

1 Ответ

2 голосов
/ 29 февраля 2020

Ваш алгоритм будет выполняться O(logn) раз, где n = dict.length, и для каждой итерации требуется O(K), где K - это максимальная (*) длина слов. Таким образом, используя мультипликативный принцип (или правило продукта , ваш алгоритм требует O(K*logn) сложности времени.

(*) Выше я указал максимальную длину, даже если внутри вашей функции вы используете math.min, но рассмотрим случай, когда вы сравниваете наибольшее слово со вторым по величине, и оба имеют длину O(K), поэтому в худшем случае это O(maximum length).

...