python - デカルト積を計算する線形時間アルゴリズム

Question

あるインタビューで、デカルト積の線形時間による解決策を考え出すように求められました。私は反復的な方法で O(mn) を実行し、これも O(mn) である再帰的なソリューションを実行しました。しかし、複雑さをさらに減らすことはできませんでした。この複雑さを改善する方法についてアイデアを持っている人はいますか? また、誰でも効率的な再帰的アプローチを提案できますか?

Answer 1

結果がありmnます。あなたがしなければならない最小限の仕事は、各結果を出力に書き込むことです。したがって、より良いことはできませんO(mn)。