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

Можно ли использовать функцию вероятности как часть вычисления сложности кода

Как включить функцию вероятности в анализ сложности кода.

if (cond1(l,n)) {
   for (int r=l;r<n;r++)
      for (int m=r;m<n;m++)
          for (int k=m;k<n;k++)
               //calculation
} else
    // calculation

Типичный анализ сложности этого кода даст сложность как O (N ^ 3).

Предположим, что cond1(l,n) в значительной степени дает false, поэтому внутренние циклы for в гипотетических вычислениях пропускаются.

Я хотел бы рассчитать сложность кода как можно точнее, потому что я хочу сравнить сложность ряда похожих алгоритмов.

Например, я хочу заменить cond1(l,n) другим набором алгоритмов, которые сокращают вызов внутреннего цикла.

Как я могу рассчитать сложность алгоритма как можно точнее.

Реалистичный сценарий кода, который я пытаюсь проанализировать, находится в [ссылка] Анализ экспоненциально-рекурсивной функции

analysis big-o code-analysis complexity-theory code-complexity
29.03.2014

Ответы:


1

Анализ сложности здесь не подходит для этой работы: он предназначен для того, чтобы дать приблизительное представление о том, что происходит по мере увеличения масштаба проблемы. Если вам нужен точный анализ времени выполнения, вместо этого вы хотите протестировать или профилировать свой код.

29.03.2014
  • Спасибо, Марк. Проблема, о которой я упоминал в [link] stackoverflow.com /questions/22468916/ на самом деле имеет сложность O(|2^N||L|) или O(|N!||L|). Однако фактическая сложность эмпирически составляет O(|N^2||L|), где функция, аналогичная cond1(), значительно сокращает рекурсивные вызовы. Есть ли способ учесть это при расчете теоретического времени работы алгоритма? 29.03.2014
  • Возможно, вам следует рассмотреть наилучший, средний и наихудший сценарии; так же, как анализируются алгоритмы сортировки. Я пытался решить ваш алгоритм (в ссылке), но я думаю, что вы должны разложить свой алгоритм как таковой. Вы должны быть в состоянии запустить его ... Попробуйте его, чтобы вывести его производительность на основе входных данных. 30.03.2014
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..