我正在努力弄清楚我擁有的一段代碼的時間復雜度，該代碼從 1 行獲取用戶輸入，例如打開 1 0，并通過空格分割輸入，然后允許用戶創建一個新的“帳戶”物件在堆上。我認為這是一個 O(n^2) 操作，因為它包含 2 個 while 回圈，加上一個額外的函式呼叫，這可能是完全錯誤的。
int main(){
std::vector <std::string> parameters;
std::string userCommand;
// Make a new account manager object for a new user
AccountManager accounts = AccountManager();
while (userCommand != "exit"){
parameters.clear(); // Clear ready for next command
std::cout << std::endl << ">>> ";
std::getline(std::cin, userCommand);
char* cstr = new char[userCommand.length() 1];
strcpy(cstr, userCommand.c_str());
char* token;
token = strtok(cstr, " ");
while (token != nullptr){
parameters.push_back(token);
token = strtok(nullptr, " ");
}
// This calls a function that creates a creates a new object on the heap
accounts.openAccount(parameters[1], parameters[2]);
}
}
uj5u.com熱心網友回復：
復雜度在空間和時間上的用戶輸入總長度是線性的。
所有單獨的操作僅在恒定的時間內迭代用戶輸入，包括內部回圈。因此，隨著n用戶輸入時間的總長度，時間復雜度為Theta(n)。
同樣，記憶體僅用于存盤用戶輸入長度的恒定倍數，這意味著Theta(n)空間復雜性。
這是假設AccountManager您沒有詳細說明的操作不占主導地位。
uj5u.com熱心網友回復：
假設n是用戶提交輸入的次數。
時間復雜度：
對于每一個n我們都在迭代多個引數，我們稱它們為m，但是在上面提供的示例代碼中，您似乎只期望兩個引數，這意味著這里的迭代始終是恒定的。如果引數的數量是可變的和/或增加時間復雜度將是O(n*m)，但如果m = 2，O(2*n)則變為O(n)線性時間。
空間復雜度：
對于每個用戶輸入n，我們正在創建一個 new account，如何從提供的代碼創建或存盤新帳戶是不明確的，但很明顯，對于每個用戶輸入，我們都會創建一個 new account，這意味著這里的空間復雜度也是O(n)。所有其他變數的空間復雜度都是恒定的，因此不會影響整體空間復雜度。
注意：該openAccount方法可以使用資料結構存盤帳戶，具體取決于哪一個，時間復雜度會受到影響。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/417237.html
標籤：
上一篇：獲取選擇排序的時間復雜度