Cosa sono O (m + n) e O (m * n) nella notazione Big O? [duplicare]

Dipende dal contesto, ma in genere m e n sono le dimensioni di due parti separate del set di dati o due proprietà separate del set di dati, ad esempio , riempiendo un array m × n . Di solito, quando la complessità dipende da due fattori indipendenti, la seconda viene denotata da m .

Quindi potremmo dire che trovare l'unione di due set è O ( m + n ), dove m e n sono le dimensioni degli input, ma trovare il loro prodotto cartesiano è O ( m · n ).

Esempio di codice:

// BOILERPLATE:
#include <array>
#include <iostream>
#include <utility>
#include <vector>

using std::array;
using std::cout;
using std::endl;
using std::ostream;
using std::pair;
using std::vector;

template<class T, class U>
  ostream& operator<< ( ostream& s, const pair<T,U>& x);

template<class T>
  ostream& operator<< ( ostream& s, const vector<T>& x );

template<class T, size_t N>
  ostream& operator<< ( ostream& s, const array<T,N>& x );
// END OF BOILERPLATE.

static const size_t M = 10, N = 5;

int main(void)
{
  static const array<int,M> a = {1,2,3,4,5,6,7,8,9,10}; // Inputs.
  static const array<int,N> b = {0,4,8,12,16};
  array<int,M>::const_iterator i = a.cbegin();  // Iterators.
  array<int,M>::const_iterator j = b.cbegin();

  vector<int> c;    // This vector will hold our results.

  // First, compute the set union of a and b,
  c.reserve(M+N);   // Which has at most M + N elements.

  while ( i < a.cend() || j < b.cend() ) {
    if ( i == a.cend() || *i > *j ) {
      c.emplace(c.end(), *j);
      ++j;
    } else if ( j == b.cend() || *i < *j ) {
      c.emplace(c.end(), *i);
      ++i;
    } else {
/* We can only have got here if: i and j are both valid and neither *i
 * nor *j is greater than the other.  Therefore, they are equal and this
 * element is a duplicate.
 */
      c.emplace(c.end(), *i);
      ++i;
      ++j;
    } // end if
  } // end while
/* The above loop terminates because it increments i, j or both at each step.
 * Provided that a and b are sorted and have no duplicates, it computes the
 * set union because it adds whichever of their next elements are smaller
 * until both are exhausted.  Since it walks each array to the end once, it
 * completes in M + N increment operations.
 */

  cout << "The set union of " << a
       << " and " << b
       << " is " << c << endl;

  c.clear();    // Done with it.

  vector< pair<int,int> > d;

  // Now, compute the Cartesian product, which has M*N elements.
  d.reserve(M*N);

  for ( i = a.cbegin(); i < a.cend(); ++i )
    for ( j = b.cbegin(); j < b.cend(); ++j )
      d.emplace(d.end(), pair<int,int>(*i, *j) );
  // We perform exactly M * N insertions.

  cout << "The Cartesian product is " << d << "."  << endl;

  d.clear();    // Done with it.

  return 0;
}

// MORE BOILERPLATE.  Not needed to understand the algorithms.

template<class T, class U>
  ostream& operator<< ( ostream& s, const pair<T,U>& x) {
    s << "(" << x.first << ", " << x.second << ")";
    return s;
  }

template<class T>
  ostream& show( ostream& s, const T& x ) {
/* Outputs a human-readable representation of an iterable container whose
 * value-type supports stream output to the stream s.
 */
    typename T::const_iterator i = x.cbegin();
    s << "{";

    if ( i < x.cend() ) {
      s << *i;
      ++i;
    }

    for ( ; i < x.cend(); ++i ) {
      s << ", ";
      s << *i;
    }

    s << "}";

    return s;
  }

template<class T>
  inline ostream& operator<< ( ostream& s, const vector<T>& x ) {
/* Outputs a human-readable representation of a vector.
 */
    return show(s, x);
  }

template<class T, size_t N>
  inline ostream& operator<< ( ostream& s, const array<T,N>& x ) {
/* Outputs a human-readable representation of an array.
 */
    return show(s, x);
  }

O (n) non significa che il tempo cresce linearmente con n. Significa che il tempo è limitato da una linea che ha qualche intercettazione Y, e alcuni tempi di pendenza n, come questo ...

... non importa quanto grande sia. Lo stesso vale per qualsiasi altro big-O. Ad esempio, O (n x m) significa che c'è una curva di delimitazione C1 + C2 x (n x m), e O (n + m) significa che la curva è C1 + C2 x (n + m).

(Tieni presente che una migliore O più grande non significa prestazioni migliori, eccetto quando n diventa grande.)

Sono rispettivamente complessità temporali lineari e subquadratiche.

Supponiamo di avere due serie di dati su cui sto eseguendo qualche operazione. Se un set ha le stesse dimensioni dell'altro, è 2n. Se è qualcosa di più o di meno è m + n. È sempre O (n), stiamo solo assicurandoci di notare che ci sono due fattori indipendenti qui. Spogliamo il 2 perché il grande O non si preoccupa delle costanti.

Subquadratic funziona in modo simile ma dipende piuttosto che indipendente. Per ogni m, fai n cose o viceversa. Così facciamo al massimo n ^ 2 operazioni. È in O (n ^ 2) ma probabilmente sarà inferiore a questo ma sicuramente più di O (n) quindi usiamo O (m * n) per renderlo chiaro.

Quindi, in sintesi, potremmo semplicemente chiamare questi O (n) e O (n ^ 2) ma in alcuni casi, in particolare quando si confrontano algoritmi molto simili, è importante avere una certa precisione di chiarezza.