import sys
final_set = []
init_set = []
for i in range(1,len(sys.argv)):
init_set.append(sys.argv[i])
for i in range(len(init_set)):
cur_min = min(init_set)
final_set.append(cur_min)
init_set.remove(cur_min)
print final_set
Этот довольно простой алгоритм сортировки должен иметь имя. Может ли кто-нибудь определить его и его временную сложность?Какой алгоритм использует этот метод сортировки?
Это, по-видимому, Selection sort, который имеет квадратичную сложность.
По всем подсчетам операций, которые я выполнил, количество операций меньше n^2. Почему это? Является ли n^2/2 тем же самым, что и n^2 в алгоритмической сложности? – user1419802
@ user1419802 Проверка минимума должна проходить через каждый элемент. – jamylak
Поскольку один элемент списка удаляется каждый раз, когда набор становится одним меньшим значением, означающим, что первая итерация принимает n операций, следующая принимает n-1 операций и так далее. Вероятно, это будет меньше n^2. – user1419802
Обратите внимание, что это списки, а не наборы. – jamylak
Да, я не думал, когда я их назвал. – user1419802