Меня попросили в интервью придумать решение с линейным временем для декартова продукта. Я сделал итерационный способ O (mn) и рекурсивное решение, которое также является O (mn). Но я не смог уменьшить сложность. Кто-нибудь есть идеи о том, как эта сложность может быть улучшена? Также может ли кто-нибудь предложить эффективный рекурсивный подход?Алгоритм линейного времени для вычисления декартова продукта
Результаты: mn; минимальная работа, которую вы должны выполнить, - записать каждый результат на выход. Таким образом, вы не можете сделать лучше, чем O(mn).
Вопрос, который приходит мне на ум, это «Линейный по отношению к чему?». Помните, что в математике все переменные должны быть определены как имеющие смысл. Замечание Big-O не является исключением. Просто говоря, что алгоритм O (n) не имеет смысла, если n не определено.
Предполагая, что вопрос был значимым, а не ошибкой, я предполагаю, что они хотели, чтобы вы попросили разъяснений. Другая возможность заключается в том, что они хотели видеть, как вы ответите, когда будете представлены с невозможной ситуацией.
Есть результаты 'mn'; минимальная работа, которую вы должны выполнить, - записать каждый результат на выход. Таким образом, вы не можете сделать лучше, чем 'O (mn)'. –
Нет. Декартово произведение дает все возможные пары, которые могут быть образованы двумя наборами, поэтому дальнейшее его уменьшение невозможно. – nhahtdh
Возможно, ваш собеседник думал об использовании квантового компьютера. –