Exercici 4 · Metodologia de la Programació UAB 2018

Exercici 4 (1 punt). Complexitat algorísmica d'elimina i buidaVector

a.

A partir del codi següent del mètode elimina de la classe Vector, determineu-ne l'ordre de complexitat algorísmica en el cas pitjor i justifiqueu la resposta:

bool Vector::elimina(int posicio)

{

bool resultat = false;

if ((posicio >= 0) && (posicio < m_nElements))

{

resultat = true;

for (int i = posicio; i < (m_nElements - 1); i++)

m_array[i] = m_array[i + 1];

m_nElements--;

if (m_nElements < (m_maxElements / 4))

{

if ((m_maxElements / 2) > TAMANY_MINIM)

{

m_maxElements /= 2;

int* aux = new int[m_maxElements];

for (int i = 0; i < m_nElements; i++)

aux[i] = m_array[i];

delete[] m_array;

m_array = aux;

}

}

}

return resultat;

}

b.

Fent ús del mètode elimina, s'implementa el mètode buidaVector següent:

bool Vector::buidaVector()

{

for (int i = 0; i < m_nElements; i++)

elimina(0);

}

Quin és l'ordre de complexitat algorísmica d'aquest nou mètode? Justifiqueu detalladament la resposta.