Сложность алгоритма, включая динамически размещаемый массив

Question

Сложность алгоритма, включая динамически размещаемый массив

Я написал программу, которая получает из пользовательского интерфейса массив чисел (натуральных чисел) и вставляет их в динамически распределяемый массив.
Я застрял в расчете биг-О программы и был бы признателен за вашу помощь в оценке этого. мое предположение 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

algorithm asymptotic-complexity c++time-complexity

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Общая сложность 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;
}

2