Calcolo della complessità

Naviga le tue risposte
-4

Ho difficoltà a calcolare la complessità di questo problema: 

REVERSE3(A): // Reverse the order of elements in an array
// P is an array; assume generating next permutation takes 1 step.


    for every possible permutation P of A:
      for index i = 1 to N:
        if P[i] is not equal to A[N-i+1]:
          continue to the next permutation
          // All elements matched in proper places
    return P

Penso che alcuni dei miei equivoci derivino dal primo ciclo. Cosa significa? Come calcoleresti la complessità per questo?

Qualsiasi aiuto sarebbe apprezzato. Grazie.

    
posta user3026388 05.04.2017 - 21:02
fonte

1 risposta

0

for every possible permutation P of A:

Questo è apparentemente una sorta di problema di scherzo, poiché questo sarebbe quasi il modo più inefficiente possibile per ordinare un array. Vogliono che passi attraverso ogni possibile ordinamento dell'array cercando quello ordinato correttamente.

In quanti modi puoi ordinare un array con elementi M? Bene, hai M scelte per la prima posizione, M - 1 scelte per la 2a posizione, ecc. Ti ricorda una funzione matematica comune?

    
risposta data 05.04.2017 - 21:52
fonte

Leggi altre domande sui tag

Impone che tutte le classi derivate e le sottoclassi definiscano sempre una funzione membro Distributività e associatività per interi con segno a 32/64 bit [chiuso]