Λάθος πολυπλοκότητα στο publib

[anastasiskolio]

Κάθε BFS έχει πολυπλοκότητα $\mathcal{O}(N + M)$ λόγω της εντολής fill, τάξης $\mathcal{O}(Ν)$ και του βρόχου while ο οποίος είναι τάξης $\mathcal{O}(M)$. Δεδομένου ότι τρέχω μια BFS για όλους τους κόμβους, η συνολική πολυπλοκότητα είναι $\mathcal{O}(N\cdot(N + M))$.

[Dim131]

Στην γενική περίπτωση έχεις δίκιο ότι είναι $O(N + M)$, αλλά επειδή η εκφώνηση λέει ότι ο γράφος είναι συνδεδεμένος έχουμε αυτομάτως ότι $M \geq N - 1$ (γιατί;), μπορούμε να γράψουμε την πολυπλοκότητα απλά ως $O(M)$.

[kbokis]

Κάθε BFS έχει πολυπλοκότητα O(N+M) λόγω της εντολής fill, τάξης O(Ν) και του βρόχου while ο οποίος είναι τάξης O(M). Δεδομένου ότι τρέχω μια BFS για όλους τους κόμβους, η συνολική πολυπλοκότητα είναι O(N⋅(N+M)).

Δες αν θέλεις και το παρακάτω παράδειγμα κώδικα:

#include <cstdio>
int M[1000000],N;//10^6
int main(){
  scanf("%d",&N);
  for(int=0;i<N;i++)scanf("%d",&M[i]);
  return 0;
}

Έστω ότι $$1\le Ν \le 100000$$.
Τι πολυπλοκότητα έχει ο παραπάνω κώδικας;