包含动态分配数组的算法复杂度
包含动态分配数组的算法复杂度
提问于 2016-01-03 01:54:15
我写了一个程序，它从用户界面获取一个数字(自然数)数组，并将它们注入到一个动态分配的数组中。我被计算程序的大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;
}回答 1
Stack Overflow用户
发布于 2016-01-03 02:19:43
总的复杂度是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;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/34568901
复制相关文章
相似问题
腾讯云开发者
