Regista6 Ответов: 3

Каждый элемент целочисленного массива заменяется произведением всех остальных элементов массива

функция >имеет два аргумента - (i) массив (ii) его размер (n)
>каждый элемент массива будет заменен произведением других элементов .
>Например, если следующий массив -{3, 2, 1}
функция вернет следующий вывод - {2,3,6}.
-это не проблема с домашним заданием . Я не хочу, чтобы ты это делал . Я просто хочу оптимизировать свою программу .
- спасибо вам.

Что я уже пробовал:

Я приложил код своей функции.
Как вы можете видеть , я использовал массив [temp] для хранения произведения элементов, но мне нужно инициализировать каждый элемент как 1 вручную .
-есть ли лучший способ сделать это ?
>Не могли бы вы дать какие-нибудь подсказки относительно того, как я могу улучшить временную сложность кода?





void multiply_input(int str[],int n)
    {
        int temp[25]={1,1,1,1,1,1,1,1,1,1,1,1,1};
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i!=j)
                    temp[i]=temp[i]*str[j];


            }

        }
        for(int k=0;k<n;k++)
            cout<<" "<<temp[k];

3 Ответов

Рейтинг:
8

Rick York

There is one way to make it not be O(n squared) and instead be O(2n) and a temporary array is not required. To do this, first calculate the product of all values in the array. That is pass one. Then step through the array again and each element will be the product divided by the element already in the array. The reason this works is, let's say we have a three element array. Item 1 is the product of items 0 and 2. To give them letters, b = a * c. To use this algorithm, the product is p = a * b * c and the new b is = p / bOld which is ( a * b * c ) / b and that reduces to b = a * c. This second pass makes it O(2n) and the only value stored is the initial product of the array.

Риск такого подхода заключается в возможности переполнения продукта. Если значения ограничены и используется шестидесятичетырехразрядный продукт, это снизит риск. Конечно, это тоже риск при подходе O(n в квадрате), но он имеет на один фактор меньше в каждом продукте. Один из его недостатков заключается в том, что результат выходит за окно, если одно или несколько значений равны нулю. Это может быть одним из ограничений, заданных для значений, хотя, например, значения должны варьироваться от 1 до 32K или что-то в этом роде. Просто так получилось, что 32K-это RAND_MAX, самое большое значение, возвращаемое rand (), поэтому его удобно использовать.

Рейтинг:
26

OriginalGriff

Для инициализации попробуйте:
Попробуй:

int temp[25];
for (int i = 0; i < 24; i++)
   {
   temp[i] = 1;
   }
Или считывать значения из файла или пользователя.

Что касается сложности времени, то это домашнее задание (нравится вам это или нет), поэтому я не дам вам никакого кода.

Но... подумайте об этом.
Сделайте один проход через весь массив, чтобы выработать произведение всех значений.
Сделайте второй проход через весь массив, чтобы заменить каждый элемент этой суммой, деленной на исходное значение ячейки.

Regista6

Дивизия была запрещена. Я уже думал о том, что такое разделение . Но ваш метод избавляет меня от ручного ввода 1 . Есть ли какой-то другой способ, который позволит резко сократить время ? .
Моя функция , я думаю, занимает приблизительно O(n^2) . Есть ли какой-нибудь способ сделать его O(n)?

Рейтинг:
15

Patrice T

Цитата:
Не могли бы вы дать какие-нибудь намеки на то, как я могу улучшить временную сложность кода?

Сложность выполнения вашего кода равна O(n2), а сложность памяти-O(2n) из-за временного массива.

При использовании метода OG (с делением) сложность выполнения равна O(n), а сложность памяти-O(n).

Поскольку единственное, что вы делаете с temp array, - это печатаете значение, вам не нужен массив, как только вы получили продукт, распечатайте его.
Сложность выполнения кода будет равна O(n2), а сложность памяти-O(n).
Если вам действительно нужно заменить значения str, это немного сложнее, но переменной с частичным произведением достаточно, чтобы сделать это.