возвести в квадрат элемент массива за время выполнения O (n) - PullRequest
Новая
       16

возвести в квадрат элемент массива за время выполнения O (n)

0 голосов
/ 05 октября 2018

Есть ли способ возвести в квадрат элементы массива с временной сложностью O (n)?Я попробовал два способа сделать это, но я думаю, что они оба O (N ^ 2) PS: я не могу использовать "*", только сложение / вычитание. 

1.
#include <stdio.h>

int squr(int n, int j){
    if(j == 0)
        return 0;
    else if(j > 0)
        return(n + squr(n, j - 1));
    else if (n < 0)
        return(n + squr(n, j - 1));
}

void loop(int* arr, int count){
    for(int n = 0; n < count; n++)
        arr[n] = squr(arr[n], arr[n]);
}

2. 
void squr(int* arr, int N){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < i; j++)
            sum += i;

        arr[i] = sum;
        sum = 0;
     }
}

1 Ответ

0 голосов
/ 05 октября 2018

Хотя маловероятно, что имел в виду OP, код может использовать размер вычисляемого указателя.Нет *.Конечно, ограничено n > 0. 

int foo(int n, char a[1][n][n]) {
  return sizeof a[0];
}

int main(void) {
  printf("%d\n", foo(5, 0));
  printf("%d\n", foo(100, 0));
  return 0;
}

Вывод 

25
10000
...