@zlodiak

Какой алгоритм эффективнее ищет минимум?

Есть два алгоритма для поиска минимального значения в неупорядоченном списке.

#!/usr/bin/env python3

def find_smallest_int(arr):
    min = arr[0]
    for i in arr:
        if i < min:
            min = i
    return min


#!/usr/bin/env python3

def findSmallestInt(arr):
    arr.sort()
    return arr[0]


Помогите пожалуйста оценить их сложность в О-нотации.

По-моему сложность первого алгоритма равна O(N). Сложность второго алгоритма я затрудняюсь определить.
  • Вопрос задан
  • 260 просмотров
Решения вопроса 1
Astrohas
@Astrohas
Python/Django Developer
первый O(N)
второй N*log(n) * C
для поиска одного минимума хорош первый
а для множественного поиска хорош второй в паре с банальным бинарным поиском
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
GavriKos
@GavriKos
С первым все правильно.
Со вторым - надо знать какую сортировку использует питон и смотреть ее сложность.
Ответ написан
BorLaze
@BorLaze
Java developer
Задача - оценить сложность алгоритмов или же действительно узнать, "какой алгоритм эффективнее ищет минимум"?

Потому как в приведенных примерах это попытка сравнить "теплое с мягким".

Первый РЕАЛЬНО ищет минимум.
Второй РЕАЛЬНО сортирует массив, а получение минимума - это побочный продукт.

Улавливаете разницу?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы