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

Question

[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). Сложность второго алгоритма я затрудняюсь определить.

Answer 1

[Astrohas]

первый O(N)
второй N*log(n) * C
для поиска одного минимума хорош первый
а для множественного поиска хорош второй в паре с банальным бинарным поиском

Answer 2

[GavriKos]

С первым все правильно.
Со вторым - надо знать какую сортировку использует питон и смотреть ее сложность.

Comments

[Andrey Tsvetkov]

какой бы алгоритм не использовал пайтон, его сложность не будет лучше чем O(N*logN)

[Владимир Олохтонов]

Andrey Tsvetkov, Только в общем случае, на небольших алфавитах можно получить линейную сложность, если использовать сортировку подсчётом.

Answer 3

[BorLaze]

Задача - оценить сложность алгоритмов или же действительно узнать, "какой алгоритм эффективнее ищет минимум"?

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

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

Улавливаете разницу?

Comments

[zlodiak]

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