Tôi đã viết một loại O (n!) Để giải trí mà không thể tối ưu hóa một cách trivially để chạy nhanh hơn mà không thay thế hoàn toàn. [Và không, tôi không chỉ ngẫu nhiên hóa các mục cho đến khi chúng được sắp xếp].Làm thế nào để viết một loại tồi tệ hơn O (n!)
Làm thế nào tôi có thể viết một loại Big-O thậm chí tệ hơn, mà không cần thêm rác không liên quan có thể được kéo ra để giảm độ phức tạp của thời gian?
http://en.wikipedia.org/wiki/Big_O_notation có nhiều thời gian phức tạp khác nhau được sắp xếp theo thứ tự phát triển.
Chỉnh sửa: Tôi đã tìm thấy mã, đây là loại xác định O (n!) Của tôi với tính năng gây cười thú vị để tạo danh sách tất cả các kết hợp của danh sách. Tôi có một phiên bản get_all_combinations dài hơn một chút để trả về kết hợp có thể lặp lại, nhưng tiếc là tôi không thể làm cho nó thành một câu lệnh đơn lẻ. [Hy vọng rằng tôi đã không giới thiệu lỗi bằng cách sửa chữa lỗi chính tả và loại bỏ các dấu gạch trong đoạn mã dưới đây]
def mysort(somelist):
for permutation in get_all_permutations(somelist):
if is_sorted(permutation):
return permutation
def is_sorted(somelist):
# note: this could be merged into return... something like return len(foo) <= 1 or reduce(barf)
if (len(somelist) <= 1): return True
return 1 > reduce(lambda x,y: max(x,y),map(cmp, somelist[:-1], somelist[1:]))
def get_all_permutations(lst):
return [[itm] + cbo for idx, itm in enumerate(lst) for cbo in get_all_permutations(lst[:idx] + lst[idx+1:])] or [lst]