oje, na escola, o professor nos pediu para implementar um algoritmo de exclusão duplicada. Não é tão difícil, e todos criaram a seguinte solução (pseudocódigo):

for i from 1 to n - 1
    for j from i + 1 to n
        if v[i] == v[j] then remove(v, v[j])    // remove(from, what)
    next j
next i

A complexidade computacional para este algo én(n-1)/2. (Estamos no ensino médio e não falamos sobre o grande-O, mas parece serO(n^2)). Essa solução parece feia e, é claro, lenta, então tentei codificar algo mais rápido:

procedure binarySearch(vector, element, *position)
    // this procedure searches for element in vector, returning
    // true if found, false otherwise. *position will contain the
    // element's place (where it is or where it should be)
end procedure

----

// same type as v
vS = new array[n]

for i from 1 to n - 1
    if binarySearch(vS, v[i], &p) = true then
        remove(v, v[i])
    else
        add(vS, v[i], p)      // adds v[i] in position p of array vS
    end if
next i

Deste jeitovS conterá todos os elementos pelos quais já passamos. Se o elementov[i] está nessa matriz, então é uma duplicata e é removido. A complexidade computacional da pesquisa binária élog(n) e para o loop principal (segundo trecho) én. Portanto, todo o CC én*log(n) se não estou errado

Então eu tive outra idéia sobre o uso de uma árvore binária, mas não consigo descartá-l
Basicamente minhas perguntas são:

O meu cálculo de CC está correto? (e, se não, por quê?) Existe um método mais rápido para isso?

Obrigad