c++ - 算法的复杂性，包括动态分配的数组

Question

我编写了一个程序，它从用户界面获取一个数字数组(自然数)并将它们注入(inject)一个动态分配的数组中。我在计算程序的大 O 时遇到了困难，非常感谢您在如何评估方面提供帮助。我的猜测是 O(nlogn) 但我不知道如何证明\显示它。

代码:

int* gradesToArr(int& arr_size, int& numOfGrades)   //function that gets parameters of initial array size (array for array of numbers received from user), and actual amount of numbers that been received.
{
    int input, counter = 0;
    arr_size = 2;
    int* arr = new int[arr_size];                   //memory allocation for initial array for the sake of interface input.


    do {                                            //loop for getting and injecting numbers from the user interface right into the Array arr.
        if (counter < arr_size)
        {
            cin >> input;
            if (input != -1)
            {
                arr[counter] = input;
                counter++;
            }
        }
        else
            arr = allocateArr(arr, arr_size);       //in case of out-of-memory, calling the function "allocateArr" that allocates twice larger memory for arr.
    } while (input != -1);

    numOfGrades = counter;                          //update the size of numOfGrades that indicates the amount of grades received from user and inserted to the array.
    return arr;
}

int* allocateArr(int Arr[], int &size)              //function that allocates bigger array in case of out-of-memory for current quantity of elements.
{
    int* fin;

    fin = new int[size * 2];                        //allocates twice more space then been before
    for (int i = 0; i < size; i++)                  //copies the previous smaller array to the new bigger array
        fin[i] = Arr[i];                            

    delete[]Arr;                                    //freeing memory of Arr because of no need, because the data from Arr moved to fin.
    size *= 2;
    return fin;
}

Answer 1

总的复杂度是O(n)。您将获得 O(log(n)) 内存分配，并且您可能会认为，每次内存分配都会获得 O(n) 操作。但事实并非如此，因为在第一次迭代中您执行的操作数量要少得多。大部分工作是复制。上次复制时，您的复制操作少于 n 次。在您进行少于 n/2 次复制操作之前的时间。在你有 n/4 复制操作等之前的时间。这总结为

n + n/2 + n/4 + ... + 2 < 2*n

单个数组元素的拷贝。因此，你有

O(2*n) = O(n)

操作总数。

简化代码

您基本上是手动实现了 std::vector 的内存管理。这会使您的代码不必要地复杂化。只需使用 std::vector 代替，您将获得相同的性能，但搞砸的风险更小。像这样:

#include <vector>
#include <iostream>

// reads grades from standard input until -1 is given and 
// returns the read numbers (without the -1). 
std::vector<int> gradesToArr()
{
    std::vector<int> result;    
    for(;;) 
    {
        int input = 0;
        std::cin >> input;
        if ( input == -1 )
            break;
        result.push_back(input);
    }
    return result;
}