какова правильная временная сложность этой функции? - PullRequest
Новая
       3

какова правильная временная сложность этой функции?

0 голосов
/ 10 октября 2019

что делает моя функция -> С учетом K отсортированных массивов, расположенных в виде матрицы. Задача состоит в том, чтобы объединить их. Вам необходимо завершить функцию mergeKArrays (), которая принимает 2 аргумента: двумерную матрицу arr [k] [k], содержащую k отсортированных массивов, и целое число k, обозначающее количество отсортированных массивов. Функция должна возвращать указатель на объединенные отсортированные массивы. 

int *mergeKArrays(int arr[][N], int k)
{

// int *merged = (int*)malloc(sizeof(int) * k * k);
// do merge sort, as individual are already sorted
// just need to merge the arrays 
int *a = arr[0];
int size_c = 2 * k;
int nb = k;
int na = k;
int *b;
int *c;
int ia, ib, ic;
for(int i = 1; i <= k - 1; ++i)
{
    // merge(x, arr[i], k * i, k)
    b = arr[i];
    c = malloc(sizeof(int) * size_c);
    if(c == NULL) exit(0);
    ia = ib = ic = 0;
    while(ia < na && ib < nb)
    {
        if(a[ia] < b[ib])
        {
            c[ic++] = a[ia++];
        }
        else
        {
            c[ic++] = b[ib++];
        }  
    }
    if(ia != na)
    {
        for(int i = ia; i < na; ++i)
        {
            c[ic++] = a[i];
        }
    }
    if(ib != nb)
    {
        for(int i = ib; i < nb; ++i)
        {
            c[ic++] = b[i];
        }
    }
    a = c;
    na = size_c;
    // printArray(a, na);
    // printf("\n");
    size_c = size_c + k;
}

return a;
}
  • Мой подход: цикл for выполняется x = (k-1) раз ....
  • каждыйВременной массив размера k объединяется с массивом размера i * k ... (k + k) + (2k + k) + .... x times
  • = (k + k + ... xраз) + (k + 1k + 2k .... x раз) = kx + kx (x-1) / 2
  • , что дает O (k ^ 3). это правильно ?
  • фактический размер arr, заданный в main, равен k ^ 2 (k по матрице k)
  • , поэтому n = k ^ 2 => k = n ^ (0.5) => T (n) = O (n ^ (3/2)) .. ??
...