Autor Tema: Sucesiones en Algoritmos

0 Usuarios y 1 Visitante están viendo este tema.

22 Mayo, 2022, 09:07 am
Leído 535 veces

eternum_loop

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 1
  • País: ar
  • Karma: +0/-0
  • Asquerosamente otaku y programador
Comento una pequeña duda que me surgió al analizar la complejidad del algoritmo de Insertion Sort

Pseudocódigo:
  \( Function \ Insertion_Sort(\ in/out \ A: \ array( \ \alpha_< \ ))  \)

  N \(  \leftarrow  \) Length(A)
  i \(  \leftarrow  \) 1

  \( while \ i \ < \ N-1 \ do:  \) //
    \(  j  \leftarrow  \) i - 1, e \(  \leftarrow  A[i]   \)   
      \(  while \ j  \ ≥  \ 0 \  \) ∧L \(  \ A[j] \ > \ e \ do:  \)
        \(  if \ A[j+1] \ \leftarrow  \ A[j] \ then  \)
                \(  j \ \leftarrow \ j-1  \)
                   \(  \ end  \ if   \)
          \(  \ end \ while   \)
     A[j+1] \(  \leftarrow  \) e
    \(  \ end \ while  \)   
\(  \ end \ Function  \)

Lo que me interesa es analizar los índices, en particular el j
entonces de forma rápida me doy cuenta que

tengo dos sucesiones de índices:
\( i_{0} = 1  \)
\( i_{k} = i_{k-1} + 1 \), al desplegar la fórmula recurrente obtengo

\( i_{k} = i_{0} + (k-1)*1 + 1 = i_{0} + k = 1 + k  \)

Ahora con \( i_{k} \) voy a definir j

\( j_{0} \) = \( i_{k} - 1  \)
\( j_{k} \) = \( j_{k-1} - 1  \)

Devuelta implemento lo anterior

\( j_{k} = j_{0} -(k-1) - 1 = j_{0} - k = j_{k} - 1, pero j_{k} = 1 + k   \)
entonces
\( j_{k} = (1+k)-k = 1  \)

La pregunta es, donde esta fallando porque esto no representa los sucesivos valores que toma j e i

\( i_{0} = 1,        i_{1} = 2,       i_{2} = 3      ...       i_{N-1} = N  \)
\( j_{0} = 1 - 1,   j_{1} = 2 - 1, j_{2} = 3 - 1 ...      j_{N-1} = N-1  \)

Porque no hay una simetría??

la sucesión \( i_{k} \) representa la toma de valores de i
pero la sucesión \( j_{k} \) no lo hace para con j y siempre es 1 sea cual sea el valor de k.

Donde N es la longitud del array