Complessità Temporale Algoritmo

xM3SS

Nuovo Utente
5
0
Salve volevo chiedervi se mi sapreste aiutare nel calcolare la complessità temporale di questo esercizio? Se possibile anche il ragionamento che è stato fatto. Grazie mille in anticipo. 🙈 🙈 🙈

C++:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> set;
vector<int> primo;

int NumPrim(int x)
{
 
  int rad = sqrt(x);
 
  for (int i = 2; i <= rad; i++)
    if (x % i == 0)
      return 0;

 
  return 1;
}

void print()
{
  int n = set.size();
  for (int i = 0; i < n; i++)
    cout << set[i] << " ";
  cout <<endl;
}

void Somma(int totale, int N, int S, int index)
{ 

  if (totale == S && set.size() == N)
  {
    print();
    return;
  }

  // ci fermiamo se il totale è maggiore di S o se l'indice ha raggiunto l'ultimo elemento 
  if (totale > S || index == primo.size())
    return;

  set.push_back(primo[index]);

  Somma(totale+primo[index], N, S, index+1);
 
  set.pop_back(); //backtrack

  Somma(totale, N, S, index+1);
}


void numPrimi(int N, int S, int P)
{
  int stop = 0;

  for (int i = P+1; i <=S ; i++) // andiamo a creare il vettore dei numeri primi da P a S
  {
    if (NumPrim(i) == 1)
      primo.push_back(i);
  }

  if (primo.size() < N)
    return;
  Somma(0, N, S, 0);
}


int main()
{
      int t;
    cin>>t;
    
    while(t--){
        int S,N,P;
        cin>>S>>N>>P;
        
        numPrimi(N,S,P);
    }

  return 0;
}
 

BrutPitt

Utente Attivo
1,166
1,262
Immagino che avrai gia' letto il REGOLAMENTO della sezione... quindi saprai che devi comunque essere tu ad iniziare il ragionamento che ti porta ad identificare il tipo di complessita' dell'algoritmo... e da li' la classe di complessita' temporale dello stesso.

A quel punto potremo poi indirizzarti meglio, o correggerti, nell'identificazione della classe temporale e cercare di dissipare eventuali dubbi.

Dirti, gia' noi, la classe di appartenenza e/o il ragionamento che ci sta dietro... sarebbe praticamente come "farti il compito".
 

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,208
1,845
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
@xM3SS procedi scomponendo il problema in parti più semplici. Qual è la complessità di NumPrim()? Quale quella di print()? E così via...

Come dice giustamente BrutPitt, riporta il tuo ragionamento e i valori che a te sembrano corretti; riporta ovviamente tutti i dubbi del caso, ma non chiedere a noi di darti i risultati (non ti sarebbero utili 😉).
 
  • Mi piace
Reazioni: xM3SS e BrutPitt

xM3SS

Nuovo Utente
5
0
Scusatemi 🙈 allora ho ragionato così:
NumPrim() --> O(rad(n)) nel caso peggiore
Print() --> O(n)
Somma() --> ho il mio dubbio ma dato che è una chiamata ricorsiva dovrebbe essere O(nlogn) nel caso peggiore
numPrimi --> per il primo for nel caso peggiore è O(n*rad(n)) + Somma() che è O(nlogn) --> nel caso peggiore quindi è O(n*rad(n))

Quindi se t = 1 --> nel caso peggiore la complessità temporale è di O(n*rad(n)). Giusto?
 

BAT

Moderatore
Staff Forum
Utente Èlite
22,668
11,451
CPU
1-Neurone
Dissipatore
Ventaglio
RAM
Scarsa
Net
Segnali di fumo
OS
Windows 10000 BUG
NumPrim() --> O(rad(n)) nel caso peggiore
tuttavia è bene precisare che l'algoritmo "ingenuo" di primalità (quello che restituisce SI/NO facendo un numero di divisioni al più pari alla radice quadrata dell'input) ha complessità pseudopolinomiale nella dimensione dell'input: in questo caso n è un valore, non la vera dimensione dell'input.
 

xM3SS

Nuovo Utente
5
0
Ah okay perfetto, invece è corretta la complessità della funzione Somma()? Non so proprio come ragionare quando sono alle prese di una funzione ricorsiva 😂😂
 

BAT

Moderatore
Staff Forum
Utente Èlite
22,668
11,451
CPU
1-Neurone
Dissipatore
Ventaglio
RAM
Scarsa
Net
Segnali di fumo
OS
Windows 10000 BUG
Non so proprio come ragionare quando sono alle prese di una funzione ricorsiva
le ho fatte troppi anni fa queste cose, per le funzioni ricorsive, a meno che non siano proprio semplici, il tempo di esecuzione si calcola ricorrendo alla soluzione di equazioni di ricorrenza (se all'università non te le hanno fatte ti avranno mostrato altri metodi)
 

BrutPitt

Utente Attivo
1,166
1,262
In NumPrim(), nel loop interno ... volendo essere precisi... ci sono sqrt(n) - 1 cilci (dato che partiamo da 2) nel caso peggiore, ma il -1 diventa trascurabile con n -> infinito.

Il calcolo dei numeri primi e' mediamente limitato dall'occorrenza del "numero primo" in funzione di sqrt(n)
(per definire "n" devi considerare che NumPrim() viene chiamato S-P volte da numPrimi).

Per cio' che riguarda Print e Somma... posso indirizzarti dicendo che non sono influenzate direttamente da n, ma dal numero dei "numeri primi" (in funzione di n).

Devi quindi fare riferimento al "teorema dei numeri primi" per trovare l'approssimazione di p(n) (dove p(n) e' il numero di "numeri primi", in funzione di n) per calcolare le complessita'

Ed aggiungo...
ricorda che parti da P e arrivi a S, quindi p(n) = p(S) - p(P)
 
Ultima modifica:
  • Mi piace
Reazioni: Andretti60

xM3SS

Nuovo Utente
5
0
Ho capito che attraverso la funzione Somma() vado a realizzare un albero binomiale, infatti se ho considero 17 1 5 come valori di input, ho come numeri primi [7,11,13,17] e ho un albero di questo tipo
0
7 11 13 17
11 13 17 13 17 17
13 17 17 17
17

e l'algoritmo ragiona così:
0->7->11->7->13->7->17->7->0->11->13->11->17->11->0->13->17->13->0->17->0->fine.
Post unito automaticamente:

1670664879902.png
 
Ultima modifica:

Ci sono discussioni simili a riguardo, dai un'occhiata!

Entra

oppure Accedi utilizzando
Discord Ufficiale Entra ora!

Discussioni Simili