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

Какова временная сложность этого вложенного цикла for?

У меня есть следующий код в питоне:

def mystery(n):
    if n <= 50 :
        for i in range(n) :
            for j in range(n) :
                print i*j
    else :
        mystery(n-1)

Для следующего вложенного цикла for:

for i in range(n) :
    for j in range(n) :

Для каждого i в n j выполняет итерацию n до i раз. Так не должна ли сложность быть O(n^2)? Однако мои коллеги говорят мне, что это не так, может кто-нибудь объяснить, почему?

python time-complexity big-o
25.01.2015

  • если n<=50 это O(n^2) ! 26.01.2015

Ответы:


1

Эти циклы выполняются только при n <= 50, поэтому они представляют собой просто краткое описание нетривиального, но постоянного объема работы. Выполняется не более 2500 операторов print. 2500, как и любая константа, не имеет значения для асимптотической сложности. Важно только поведение в пределе (т. е. при неограниченном росте n).

Для больших n функция просто ведет обратный отсчет от n до 50. Эта часть занимает O(n) времени, поэтому временная сложность mystery в целом является линейной.

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