Учитывая диапазон, я должен рассчитать частоту чисел в массиве. Является ли данное решение эффективным?

Question

#include<iostream.h>

int main()
 {
   int a[10]={1,2,3,5,2,3,1,5,3,1};
   int i;
   int c[10]={0};

   for(i = 0 ; i < 10 ; i++)
       c[a[i]]++;

   for(i=0;i<10;i++)
      cout<<i<<": "<<c[i]<<endl;

   return 0;
 }

Время работы Алгоритма составляет O (n), но оно занимает дополнительное пространство O (n). Могу ли я сделать лучше?

Спасибо! * * 1004

Answer 1

Зависит от того, что для вас важно - вы можете создать алгоритм, занимающий O (n ^ 2) времени, но O (1) пространство (используя два цикла, см. Код ниже), но вы не можете улучшить сложность времени нижеO (n).

for(i=0;i<10;i++) {
  count = 0;
  for(j=0;j<10;j++)
    if (c[j] == i) count++;
  cout<<i<<": "<<count<<endl;
}

Другой возможностью для пространства O (1) будет сортировка массива на месте и последующее его прохождение один раз, что должно иметь временную сложность O (n log n) с использованиемсортировка по месту слияния.

Answer 2

Если все числа находятся в диапазоне от 1 до n, то это можно сделать за O (n) сложность времени и O (1) сложность пространства.

, если есть индекс X и массив A, такие чтоA [X] = Y, затем добавьте N к значению, присутствующему в индексе Y. Так что A [Y] становится A [Y] = оригинал + N.Продолжая это, значения будут иметь форму (оригинал + KN), где k> = 0. Чтобы извлечь оригинальный элемент, мы можем сделать (оригинал + KN)% N, так как (x + kn)% n = x, и число можно найти с помощью (оригинал + KN) /N.

Answer 3

Что такое "эффективный"? Покажите нам свои требования к производительности и измерения производительности. Тогда мы можем сказать вам, если это эффективно. До этого это широко открытый вопрос с множеством неправильных ответов и без правильных ответов. Пока что ответы верны, только слово «эффективный» означает «бежит как можно быстрее».

Возможно, у вас быстрый компьютер с небольшим объемом оперативной памяти.

Вы всегда можете заставить часть кода работать быстрее или использовать меньше памяти с меньшим дисковым пространством или меньше .... если он недостаточно «эффективен», я видел, как парни производили сборку вручную, чтобы сделать это быстрее. Обычно это пустая трата времени и усилий. Оптимизация кода, который не был профилирован, - игра для дураков.

Answer 4

Нет, ты не можешь.Это лучшее, что ты можешь сделать.