Publish your project for free and start receiving offers from freelance contractors in serveral minutes after publication!
500 ₴

Задача - алгоритм

project complete


Дан алгоритм

boolean myst(int[] A) {

int n = A.length;

for (int i = 0; i < n-1; i++) {

for (int j = i+1; j < n; j++) {

for (int k = 0; k < n; k++) {

if (A[i] * A[j] == A[k]) {

return true; }

}

}

}

return false;

}

Необходимо разработать алгоритм, который будет искать то же что и этот, только за гораздо меньшее время (рекомендуется использовать спец. тип данных), я так подозреваю Hash

Отзыв заказчика о сотрудничестве с Даниилом Мунтяном

Quality
Professionalism
Price
Availability
Terms

Не в первый раз работаю с исполнителем, все четко и в срок. Очень рекомендую

Отзыв фрилансера о сотрудничестве с Сергеем Поповым

Payment
Task formulation
Requirements
Availability

Уже несколько раз работал с заказчиком, очень четкие задачи и, что немаловажно - быстрая обратная связь, что позволяет оперативно решать разные вопросы по выполнению.
Рекомендую сотрудничать

Даниил М. Даниил Мунтян | Safe Safe



  1.  freelancer isn't working in the service any longer
  2. 2 days1 000 ₽
    Дмитрий Иванков
     195   2  0

    Могу на ассемблере вставку написать
    ===============================================================
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    https://vk.com/cyber4401
    [email protected]

    Belarus Minsk | 23 August 2018 |
  3. 1 day150 ₴
    Eduard Karpets
     1637   36  1   1

    Сделаю на питоне. Но может что то дополнительно известно о входящем массиве - например, отсортирован или что то известно о его значениях - например есть диапазон. Такие данные могут помочь в оптимизации.

    Ukraine Kyiv | 24 August 2018 |
  4. 1 day300 ₽
    Александр Родионов
     481   9  0

    Здравствуйте. Готов предложить Вам решение со сложностью тета от (n + n^2). Реализация на необходимом Вам языке (кроме сильно специфичных или ассемблера). Эффективность оптимизации - для теста на c# на массиве 1000 элементов, 10000 итераций, запущенного на моем ноутбуке, среднее время улучшилось в ~5 раз

    Russia Saint-Petersburg | 23 August 2018 |
  5. 1 day500 ₴
    Володимир Соколов
     1589   82  2   5

    Предлагаю ускорить его в n раз относительно того что есть, реализую на C#
    или накидаю псевдокод и реализуете на любом другом языке програмирования

    Ukraine Lvov | 24 August 2018 |
  6. 1 day1 000 ₽
    Сергей Петров
     253   3  1   3

    Есть идея как это сделать гораздо быстрее. Есть требования восколько нужно уменьшить время поиска?

    Ukraine Odessa | 24 August 2018 |
  7. 1 day100 ₴
    Дмитрий Зелинский
     228 

    Максимально оптимизирую алгоритм с использованием хеш-таблицы. Есть ли дополнительное ограничение на диапазон чисел или порядок в массиве ?

    Ukraine Kamenets-Podolskii | 24 August 2018 |
  8. 1 day500 ₴Winning proposal
    Даниил Мунтян
     333   5  1

    Добрый день, имею опыт в подобных задачах, готов приступить к выполнению)

    Ukraine Kyiv | 26 August 2018 |
  • вы б лучше рассказали что делать должен алго, а не давали то что не подходит

  • Согласен. Физику задачки в студию

  • Сергей Попов — project author
    Complain | 23 August 2018 |

    а разве не понятно что она делает?

  • конечно понятно, но чтоб что то улучшить надо знать что надо, раз уж то что вы накодили не то

  • Смотрит произведение пар и сравниет если есть такой в массиве

  • точнее не пар, а всех элементов один с другим по всей длине массива

  • Сергей Попов — project author
    Complain | 23 August 2018 |

    Так и есть, вопрос как написать так, чтобы он это делал быстро

  • Так вот чтобы такие вещи оптимизировать по быстродействию, обычно и используют какую-то априорную информацию, вытекающую из задачи, а не из "медленного" алгоритма. Есть, например, много задач в вычислительной математике, которые сводятся к "трехдиагональным" матрицам, в которых значащие элементы есть только на трех диагоналях, все остальные элементы - нули. Очевидно, что нечего тратить пустые проходы циклов на нули. Не вопрос, прикладные математики посидели и забацали метод прогонки, который на нули вобще внимания не обращает. 

    Это и дает реальное ускорение. А так...

  • Сергей Попов — project author
    Complain | 23 August 2018 |

    Ребят, задача прям так и стоит, как написана, с выданным алгоритмом))

  • а какой диапазон значений?

  • Сергей Попов — project author
    Complain | 23 August 2018 |

    В смысле? о чем речь? а диапазоне значений чего?

  • если б не посмотрел топик еще разок так и не узнал бы что ответили
    диапазон значений масива имел ввиду, если диапазон меньше размера масива, то есть несколько вариантов увеличить быстродействие, но сейчас сделал ставку с предложением увеличить быстродействие в n раз вне зависимости от данных

  • Эд фамилия
    Complain | 23 August 2018 |

    заря-лейпциг 0-0

    заря с 17 минуты в меньшинстве

  • Сортируете исходный массив по возрастанию, потом во внутреннем цикле рассматриваете только значения j<=i, k<=j. Уже будет ускорение. 

    Обращение к элементам массива делать через инкрементируемые указатели. 

    Это уже даст ускорение. 

    Если размер массива невелик, то можно составить косую матрицу предрасчитанных произведений. 

  • Eduard Karpets
    Complain | 24 August 2018 |

    А как с отрицатеными значениями?