Calcul de la notation Big-O de cet ensemble constitué de plusieurs classificateurs

Question

J'ai un modèle ci-dessous, et j'essaie de calculer sa complexité globale de calcul (notation Big-O).

Dans ce modèle, les classificateurs de type « A » ont une complexité en temps de O(mN), où N est le cas, le numéro du jeu de données, et m est une variable constante déterminée par le classificateur « A » (J'essaie de produire un exemple de travail minimal pour que la question soit claire: faites-moi savoir si vous avez besoin de plus d'informations sur m). Le classificateur "B" a une complexité temporelle de O(N^2), où N est le nombre d'instances dans l'ensemble de données.

Ce modèle est fondamentalement un classificateur d'ensemble composé d'un nombre n de classificateurs "A" et d'un nombre m de classificateurs "B". La décision finale est basée sur un simple vote majoritaire pondéré. Pour déterminer les poids, j'ai formé le système en utilisant un ensemble de données, tout en affectant des combinaisons de poids générées aléatoirement aux classificateurs "A" et "B". La meilleure combinaison de poids sélectionnée pour le système est celle qui offre la meilleure précision de détection sur le sous-ensemble de formation de l'ensemble de données. Cette combinaison de poids sélectionnée est ensuite utilisée lors du test du système. Étant nouveau pour les algorithmes et l'analyse de complexité temporelle, je n'ai pu calculer ou étudier que les complexités temporelles des classifications individuelles que j'ai présentées/énoncées ci-dessus, mais quelle est la complexité globale de calcul du système étant donné le n + m les classificateurs et la phase de vote majoritaire (phase de décision finale)?

Answer 1

Soit a_1, a_2, a_3, a_4, ...., a_n les constantes générées par les classificateurs n de type A.

Laissez a_max = max{a_1, a_2, a_3, ...., a_n}

La complexité de temps pour les n classificateurs de type A est: O(n*a_max*N)

---

m classificateurs de type B, chacun fonctionnant en temps complexité O(N^2)

Pour le total m classi FIERS ce serait: O(m*N^2)

---

Complexité: O (m * N^2 + n * a_max * N)

---

Vous auriez pu aussi l'écrire:

O(m*N^2 + (a_1 + a_2 + a_3 + ... + a_n)*N), a tighter bound.