Оптимизация очень простого алгоритма O (n^3) для алгоритма O (n^2).

Я застрял в этом вопросе очень долго. Пусть X, Y и Z - множества из n целых чисел. Пусть k - любое целое число. Вопрос «Можете ли вы найти x в X, y в Y и z в Z, что x + y + z = k", очевидно, можно решить в O (n^3) раз, попробовав все комбинации. Дайте алгоритм, который работает в O (n^2). Вы можете предположить, что сортировка - это встроенный метод, который работает в O (n * log n) времени. Это был вопрос из старого теста. Любая помощь будет оценена. Благодарю.Оптимизация очень простого алгоритма O (n^3) для алгоритма O (n^2).

источник

2014-09-26 ad56

Вы также можете думать об этом так: если * x *, * y * и * k * известны, есть ли способ проверить, является ли * z * элементом из * Z * эффективно? – Groo

Сортировка массива.

Для каждого z массива проверьте, является ли k-z суммой двух элементов, в O (n) времени (классический вопрос и решение для интервью, вы найдете много страниц, содержащих это).

источник

2014-09-27 05:29:52

Итак, я сортирую все массивы, а затем для каждого z из Z проверяю, является ли kz суммой x в X и ay в Y. Этого легко достичь в O (n), если X и Y отсортированы и, следовательно, общее время O (n^2), потому что вы должны сделать это для всех n элементов в Z. Исправить? – ad56

Любая справка будет полезна.

Моя помощь в виде подсказок.

Подсказки:

1 - Если x + y + z == k, то z = k - x - y ...

2 - Как вы можете проверить на членство в множестве O(1)? (Который игнорирует подсказку в вопросе ...)

ИЛИ

2a - Что O(N log N) когда N является M * M? (И почему я выбрал O(N log N) ??)

источник

2014-09-26 04:37:55

Это очень расплывчатый намек, вам все равно придется циклически перебирать три массива, что делает его _still_ O (n^3). Возможно, в интересах предоставления _useful_ ответов вы могли бы немного разъяснить :-) – paxdiablo

Нет ... вы этого не делаете. Вопрос содержит другой факт. Мой ответ указан в том виде, в котором он заинтересован в том, чтобы заставить ОП задуматься об этом, что, вероятно, больше в * своих интересах, чем предоставление горшечного ответа. –

Я не собираюсь голосовать за тебя, С, так как я понял. Но у меня есть довольно много лет под моим поясом :-) ОП не может этого добиться. Даже если вы указали на этот дополнительный факт, он может пойти каким-то образом, чтобы ответить на уровень OPs, все еще требуя некоторой мысли. ... Неважно, вы добавили его во время моего комментария. – paxdiablo

Оптимизация очень простого алгоритма O (n^3) для алгоритма O (n^2).

ответ

Смежные вопросы