Алгоритми та структури даних · Senior · Запитання 63 з 75
Яка складність Array.prototype.sort у V8 на вже відсортованому масиві?
- ✓Правильна відповідь: Близько O(n)
- 2O(n log n) без жодних скорочень
- 3O(n²)
Пояснення
Timsort бачить, що весь масив - одна зростаюча серія, і робить лише лінійну перевірку. Це одна з причин віддавати перевагу вбудованому сортуванню перед власним quicksort.