#machine-learning #time-complexity #knn #naivebayes #computation
#машинное обучение #временная сложность #knn #наивные высказывания #вычисление
Вопрос:
Если временная сложность некоторых алгоритмов машинного обучения, таких как; kNN и наивный Байес, может быть определена как O (N * P), где N — количество строк, а P — размер объекта, какой большой сложности O это считается?
Относится ли временная сложность O (N * P) к той же категории, что и O (N), следовательно, это «Линейная сложность»? Если P = N было истинным, не могло ли это также считаться как O (N ^ 2), следовательно, квадратичная сложность? Итак, какую именно сложность мы можем назвать, она не определена? Спасибо.
Ответ №1:
Как вы сказали, это зависит от значения P
. Следовательно, временная сложность O(N*P)
в целом, и вы можете объяснить это более подробно, когда мы узнаем больше о значении P
. Для другого примера, чем вы упомянули, если P = N^2
временная сложность также может быть кубической. Поэтому вы ничего не можете сказать об этой временной сложности, не зная о. P