代替乘法的大O - 遞歸

使用替代乘法的方法。代替乘法的大O - 遞歸

public static int mult(int num, int repeat){ 
     if (repeat == 0) return 0; 
     if (repeat == 1) return num; 
     return num + mult(num, repeat - 1); 
    }

在時間和空間複雜性方面，這會是O（k）的時間，其中k是重複和O（1）空間？

來源

2017-01-22 Bao Thai

*「使用一種方法取代乘法」* - 爲什麼？ – jonrsharpe

面試問題，並非真正取代運營商。只是在我的遞歸技能工作@jonrsharpe –

@Snorehorse我的道歉，那麼我會如何移動？我剛剛在這裏看到很多Big o的問題，所以我認爲這是允許的 –

這是O（K）時間，因爲您將根據repeat調用該函數一次，每次調用都是O（1）。然而，它也是O（k）空間，在達到終止條件之前（在沒有尾調用遞歸優化的情況下），您將擁有k個堆棧幀。

來源

2017-01-22 22:50:46

糾正我，如果我錯了，但尾遞歸不能在這裏適用作爲'num'必須保留，直到從遞歸調用中返回，所以持有'num'的棧幀不能被丟棄。 – Arkadiy

這裏是一個尾遞歸兼容版本：http://stackoverflow.com/questions/1149150/tail-recursive-method-to-multiple-2-numbers – Arkadiy

@Arkadiy一個好的優化器可能會告訴'num'不會完全改變，所以我認爲尾遞歸可能適用。我不知道是否有那麼聰明。如果它像'num + mult（num - 1，repeat - 1）'這會改變事物[雖然這當然不再是乘法]。 – ajb

代替乘法的大O - 遞歸

回答

相關問題