Nano Hash - криптовалюты, майнинг, программирование

поиск элементов в массиве, которые имеют большие признаки, но меньшее значение в массиве

Я хочу найти количество элементов в массиве, которые имеют следующие два условия:

  1. 1 <= i < j <= n
  2. a[i] > a[j]

Я использую следующий код, но мне нужен более быстрый совет?

for(int i=0; i<n; i++){
    for (int j=i+1; j<n; ++j){
        if (a[j] < a[i])
            ans++;
    }
}
c++ algorithm time-complexity
11.01.2020

  • Один совет; Независимо от того, какой алгоритм вы используете, протестируйте сборку вашего кода с включенной оптимизацией (также известной как сборка Release). Не тестируйте отладочную сборку по умолчанию. Оптимизация компилятора может иметь большую разницу в производительности. 11.01.2020
  • Когда вы говорите быстрее, вы имеете в виду асимптотически быстрее для массивов большого размера или о каком размере массива мы говорим? 11.01.2020
  • @walnut да, я имею в виду асимптотически для больших размеров массива 11.01.2020
  • @JesperJuhl, я помню, спасибо за подсказку :) 11.01.2020
  • Отвечает ли это на ваш вопрос? Найдите количество неупорядоченных пар в массиве или Подсчет инверсий в массиве 11.01.2020
  • @walnut да вот и спасибо за твою помощь :) 11.01.2020

Ответы:


1

То, что вы пытаетесь сделать, называется счетчиком инверсий. Асимптотически сложность вашего текущего алгоритма равна O(n^2). Вы можете сделать это за O(nlogn) время, используя подход «разделяй и властвуй», основанный на сортировке слиянием. Подробнее об этом читайте здесь.

11.01.2020
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..