Time/space 字符串的复杂性 splitting/object 在 C++ 中创建

Question

我正在努力计算我拥有的一段代码的时间复杂度，该代码从 1 行获取用户输入，例如打开 1 0，并通过空格拆分输入，然后允许用户创建一个堆上的新 'account' 对象。我认为这是一个 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]);
    }
}

Answer 1

在 space 和时间上，复杂度与总用户输入长度成线性关系。

所有单独的操作仅对用户输入进行固定次数的迭代，包括内循环。因此n用户输入时间的总长度时间复杂度为Theta(n).

同样，内存仅用于存储用户输入长度的常量倍数，这意味着 Theta(n) space 复杂性。

这是假设您没有详细说明的 AccountManager 操作不占主导地位。

Answer 2

我们假设 n 是用户提交输入的次数。

时间复杂度：

对于每个 n 我们迭代了一些参数，我们称它们为 m，但是在上面提供的示例代码中，您似乎只需要两个参数，这意味着这里的迭代是永远不变。如果参数的数量是可变的 and/or 增加时间复杂度将是 O(n*m)，但是如果 m = 2，O(2*n) 变成 O(n) 线性时间。

Space 复杂度：

对于每个用户输入 n 我们正在创建一个新的 account，从提供的代码中创建或存储新帐户的方式不明确，但很明显对于我们创建的每个用户输入一个新的 account，意味着这里的 space 复杂度也是 O(n)。所有其他变量的 space 复杂度是恒定的，因此不会影响整体 space 复杂度。

注意： openAccount 方法可以使用数据结构存储帐户，具体取决于哪个时间复杂度会受到影响。

Time/space 字符串的复杂性 splitting/object 在 C++ 中创建

Time/space complexity of string splitting/object creation in c++

c++

algorithm

time-complexity

space-complexity