Newsgroup: it.scienza.informatica
Titolo: aiuto per algoritmo

Si consideri il problema di determinare se in un array A[1..n] di
interi positivi esistono due elementi A[i] e A[j] tali che A[i] × A[j]
= k, per un intero fissato k.
Descrivere ed analizzare un algoritmo che risolva il problema in tempo
O(n) nell'ipotesi che l'array sia ordinato.
Ho cercato di fare in questo modo:
for i=1 to n-1 do
   trova con la ricerca binaria in A[i+1 n] l'elemento k/A[i]
   se l'elemento è stato trovato esci dal ciclo(se tale elemento
esiste moltiplicato per A[i] da k)
L'algoritmo però ha complessità O(nlogn) e io cerco uno di complessità
lineare...Secondo voi esiste?

arius81 ha scritto:

Nella mia precedente email c'era un errore.
Esempio:
2
4
5
7
8
10
12
48
50
Sia K = 40
C = 0
D = A.size() -  1 = 8
Q1 = K/A[C] = 40 / 2 = 20
Q2 = K/A[D] = 40 / 50 = 0
essendo A[D]>Q1 posso decrementare D : D = 7
non essendo A[C]<Q2 lascio invariato C
----------
Q1 = K/A[C] = 40 / 2 = 20
Q2 = K/A[D] = 40 / 48 = 0
essendo A[D]>Q1 posso decrementare D : D = 6
non essendo A[C]<Q2 lascio invariato C
----------
Q1 = K/A[C] = 40 / 2 = 20
Q2 = K/A[D] = 40 / 12 = 3
essendo A[D]>Q1 posso decrementare D : D = 5
essendo A[C]<Q2 posso incrementare C : C = 1
----------
Q1 = K/A[C] = 40 / 4 = 10
Q2 = K/A[D] = 40 / 10 = 4
essendo A[D]==Q1
essendo A[C]==Q2
ho trovato i due numeri che cercavo

arius81 ha scritto:

Mi è venuta in mente al volo questa possibile soluzione.
Attenzione verifica bene perchè non sono sicurissimo.
Esempio:
2
4
5
7
8
10
12
48
50
Sia K = 40
C = 0
D = A.size() -  1 = 8
Q1 = K/A[C] = 40 / 2 = 20
Q2 = K/A[D] = 40 / 50 = 0
essendo A[D]>Q1 posso decrementare D : D = 7
essendo A[C]>Q2 lascio invariato C
----------
Q1 = K/A[C] = 40 / 2 = 20
Q2 = K/A[D] = 40 / 48 = 0
essendo A[D]>Q1 posso decrementare D : D = 6


 lineare...Secondo voi esiste?
potresti usare due puntatori al primo ed ultimo elemento della lista e
nel caso il prodotto sia <k spostare il primo oppure al contrario il
secondo...
mi spiego meglio con il codice:
def mulk(k,A):
    i=0
    j=len(A)-1
    while i<=j:
        mul=A[i]*A[j]
        if mul==k:
            return True
        if mul<k:
            i=i+1
        if mul>k:
            j=j-1
    return False
assert(mulk(21,[3,5,7,11]))
assert(mulk(25,[1,5,7,9]))
assert(not(mulk(21,[1,3,5,9])))
è lineare perchè ad ogni passo un puntatore si sposta


nell'ipotesi k>A[n] con l'array ordinato con relazione di ordine crescente 
(A[i]<=A[j] per i,j in [1..n])
determina se esistono almeno 2 elementi soddisfacenti
for each i from n to 1
        if  (k mod A[i] == 0) and (exist A[j] con j in [1..i-1]   tale che 
A[j] = k/A[i])
                exit with true for values A[j] e A[i]
si ha che A[j] * A[i] = k
exist sarà una funzione che scorre l'array con indice da i-1 a 1 cercando il 
valore risultato della divisione;
viene eseguita solo quando si trova un divisore per k
mod è il modulo :-)
quindi la complessità è O(n)

 quindi la complessità è O(n)
a me il tuo algoritmo pare proprio O(n²)

 a me il tuo algoritmo pare proprio O(n�)
In effetti quell'algoritmo ha complessit� O(n^2), come puoi vedere
nell'esempio che k = 21 ed il vettore � [3, 3, 3, 3, 3, 3, 3].
Invece, si pu� procedere cos�:
i = 1
j = n
trovato = falso
esegui
	prodotto = A[i] * A[j]
	se prodotto < k
		i = i + 1
	altrimenti se prodotto > k
		j = j - 1
	altrimenti
		trovato = true
mentre trovato == false e i <= j
restituisci trovato
che � lo stesso del tuo post precedente che non avevo letto prima di
scrivere queste righe :-).
Aggiungo che, volendo essere ancora pi� furbi, si pu� procedere cos�:
i = 1
j = n
trovato = falso
esegui
	prodotto = A[i] * A[j]
	se prodotto < k
		esegui
			i = i + 1
		mentre k mod A[i] <> 0 e i <= j
	altrimenti se prodotto > k
		esegui
			j = i - 1
		mentre k mod A[j] <> 0 e j >= i
	altrimenti
		trovato = true
mentre trovato == false e i <= j
restituisci trovato
in questo caso per� la complessit� nel caso peggiore � sempre O(n).
Credo sia interessante, e non banale, calcolare invece la complessit�
nel caso medio.