Сложность времени одного алгоритма, каскадного в другое?

Question

Я работаю со случайным лесом для контролируемой проблемы классификации, и я использую алгоритм кластеризации k-mean для разделения данных на каждом узле. Я пытаюсь вычислить временную сложность алгоритма. Из того, что Я понимаю, что временная сложность для к-средств является

О (п & Мидот, K & Мидот; я & Мидот; д)

где

• п есть число точки,
• К числу кластеров,
• Я это число итераций, и
• д это количество атрибутов.

K, I и d являются константами или имеют верхнюю границу, а n намного больше по сравнению с этими тремя, поэтому я полагаю, что сложность - это просто O (n).

Случайный лес, с другой стороны, является подход с разделением и победой, поэтому для n экземпляров сложность O (n & middot; logn), хотя я не уверен в этом, исправьте меня, если я неправильно.

Чтобы получить сложность алгоритма, я просто добавляю эти две вещи?

Answer 1

В этом случае вы не добавляете значения вместе. Если у вас есть алгоритм разделяй и властвуй, среда выполнения определяется комбинацией

• Число подзадач, сделанных на вызов,
• Размеры этих подзадач и
• Объем работы сделано для каждой проблемы.

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

В вашем случае вы начинаете с алгоритма разделения и покоя, где все, что вы знаете, это то, что среда выполнения O (n log n) и добавляет шаг, который выполняет O (n) на уровень. Просто зная это, я не думаю, что можно определить, какова будет время исполнения. Если же, с другой стороны, вы делаете предположение, что

• Алгоритм всегда разделяет вход на две более мелкие куски,
• алгоритм рекурсивно обрабатывает эти две части независимо друг от друга, и
• Алгоритм использует свой вывод (n), чтобы определить, какой раскол сделать

Тогда вы можете заключить, что время выполнения - O (n log n), так как это решение для повторения, заданного Главной теоремой.

Без дополнительной информации о внутренней работе алгоритма, однако, я не могу сказать наверняка.

Надеюсь, это поможет!