計算笛卡爾乘積的線性時間算法

我在採訪中被問到提出了一個笛卡兒積的線性時間解決方案。我做了迭代方式O（mn）和一個也是O（mn）的遞歸解決方案。但我無法進一步降低複雜性。有沒有人有關於如何改進這種複雜性的想法？也有人可以提出一個有效的遞歸方法？計算笛卡爾乘積的線性時間算法

2013-02-26 gizgok

有'mn'結果;你必須做的最小工作是將每個結果寫入輸出。所以你不能比'O（mn）'做得更好。 – 2013-02-26 00:17:51

編號笛卡爾產品給出了所有可能由2組形成的對，所以不可能進一步減少它。 – nhahtdh 2013-02-26 00:18:33

也許你的面試官正在考慮使用量子計算機 – 2013-02-26 00:21:11

還有mn結果;你必須做的最小工作是將每個結果寫入輸出。所以你不能比O(mn)做得更好。

2013-02-26 01:05:04

我腦子裏想到的這個問題是，「關於什麼是線性的？」請記住，在數學中，所有變量都必須定義爲有意義。大O符號也不例外。如果沒有定義n，簡單地說一個算法是O（n）是毫無意義的。

假設問題是有意義的，而不是一個錯誤，我的猜測是他們希望你要求澄清。另一種可能性是，他們想要看到在遇到不可能的情況時你會如何迴應。

2013-11-23 19:00:25

回答