ПК
Не существует детерминированной сортировки, которая работает за линию в общем случае
То, о чём говорит Павел понимаю.
Но есть ведь Radix sort.
Который сортирует за линию.
Потому хочу узнать, может существует другой способ.
Size: a a a
2020 September 01
V🇺
radix sort опирается на дополнительную структуру (целочисленность с фиксированной точностью)
S
radix sort опирается на дополнительную структуру (целочисленность с фиксированной точностью)
Но задачи сортировки ведь выполнена. Хоть и использует дополнительную структуру.
И это ввело в ступор.
И это ввело в ступор.
V🇺
Но задачи сортировки ведь выполнена. Хоть и использует дополнительную структуру.
И это ввело в ступор.
И это ввело в ступор.
структуру задачи, не структуру данных
EZ
Но задачи сортировки ведь выполнена. Хоть и использует дополнительную структуру.
И это ввело в ступор.
И это ввело в ступор.
Но не в общем случае
V🇺
Но задачи сортировки ведь выполнена. Хоть и использует дополнительную структуру.
И это ввело в ступор.
И это ввело в ступор.
если хочешь convex hull за линию, нужно тоже какую-то дополнительную структуру в задачу ввести (например что точки даны в порядке обхода валидного многоугольника)
S
Обдумаю и вернусь.
2020 September 02
ПК
printf является Turing-complete
ВВ
Есть замечательная статья о неожиданных проявлениях полноты по Тьюрингу — https://www.gwern.net/Turing-complete
2020 September 03
V🇺
Есть замечательная статья о неожиданных проявлениях полноты по Тьюрингу — https://www.gwern.net/Turing-complete
отлично
2020 September 05
d
вот набижали
S
вот набижали
так учебный год же начался :)
SC
вот набижали
Главное, чтобы не с одним и тем же вопроусом
ПК
Главное, чтобы не с одним и тем же вопроусом
>Правда ли, что P=NP при N=1?
S
>Правда ли, что P=NP при N=1?
SC
В одном чате доказали гипотезу Римана квадратом суммы.
П
Вопрос. Условие задачи - размер массива чисел равен 1000. Нужно найти максимум в таком массиве. Сложность алгоритма будет O(1) или O(n)?
d
Вопрос. Условие задачи - размер массива чисел равен 1000. Нужно найти максимум в таком массиве. Сложность алгоритма будет O(1) или O(n)?
в общем случае O(n)
d
но если известно что он отсортирован по значениям за O(1)