O (NlogN) нахождение 3 чисел, которые имеют сумму любого произвольного T в массиве
Я никогда не слышал о Droid Sans Mono прежде, но я установил его и попробовал его в 9 точках, и я должен сказать, что это - безусловно моно шрифт высшего качества, который я видел на Linux.
На моем Mac это является Паническим Без полностью, использование его в 11 или 12 точках позволяет сглаживаться, это на самом деле продолжает работать моноширинное, который я никогда не видел прежде.
3 ответа
Я думаю, что это просто сумма подмножества проблема
Если да, то это NP-Complete.
РЕДАКТИРОВАТЬ: Неважно, это 3 сумма, как указано в другом ответе.
Звучит как домашний вопрос ...
Если вы можете найти два значения, которые в сумме составляют N , но вы хотите расширить поиск до трех значений, не могли бы вы для каждого значения M в наборе искать два значения, которые в сумме дают (N - M) ? Если вы можете найти два значения, которые в сумме дают определенное значение за время O (log N), то это будет O (N log N).