Влияет ли общая временная сложность алгоритма, если он вызывает другой алгоритм для выполнения своих функций? - PullRequest
Новая
       8

Влияет ли общая временная сложность алгоритма, если он вызывает другой алгоритм для выполнения своих функций?

0 голосов
/ 07 ноября 2018

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

Если я напишу отдельный метод, который использует алгоритм сортировки, чтобы сначала отсортировать массив, а затем вернуть наименьшее, повлияет ли это на временную сложность алгоритма?

Вот мой код: 

private static int nonSmallestElement(int[] array) {
    int smallest = smallestElement(array);
    int index = (int) (array.length * Math.random());
    System.out.println("Index = " + index);
    for (int i = index; i < array.length; i++) {
        if (array[i] != smallest) {
            return array[i];
        }
    }
    return array[1];
}

private static int smallestElement(int[] array) {
    Arrays.sort(array);
    return array[0];
}

Здесь в методе Arrays.sort() используется алгоритм двухшаговой быстрой сортировки, который равен O (n log (n)). Означает ли это теперь, что метод nonSmallestElement() также принимает эту временную сложность, или это O (1), потому что он не должен обрабатывать сортировку?

1 Ответ

0 голосов
/ 07 ноября 2018

Вы правы, вам нужно посчитать все действия, чтобы рассчитать сложность алгоритма. Но вы должны знать о правилах, например, большее включает меньшее ( больше примеров ). В вашем случае вы звоните smallestElement() один раз - O (nlogn), а затем получаете цикл O (n). В результате общая сложность будет O (n + nlogn). Но final сложность nonSmallestElement() - это O (nlogn), потому что nlogn больше.

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

Обновление от комментариев:

Вот подсказка: если у вас в руках два разных значения, то большее не должно быть наименьшим значением в массиве. Для «типичный» массив, который вы ожидаете найти два различных значения в любых двух элементы. @James K Polk

...