algorithm - qué - notacion big o

Análisis asintótico

Question

Tengo problemas para entender cómo convertir esto en una fórmula.

 for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j += i) {

Me doy cuenta de lo que sucede, por cada i ++ tienes 1 nivel de multiplicación menos de j.

i = 1, obtienes j = 1, 2, 3, ..., 100

i = 2, obtienes j = 1, 3, 5, ..., 100

No estoy seguro de cómo pensar esto en términos de Big-theta.

El total de j es N, N / 2, N / 3, N / 4 ..., N / N (Mi conclusión)

¿Cómo sería mejor tratar de pensar esto como una función de N?

Answer 1

Entonces, tu pregunta puede reducirse a "¿Cuál es el límite apretado para la serie de armónicos 1/1 + 1/2 + 1/3 + ... + 1 / N?" Para lo cual la respuesta es log N (puede considerarlo como suma continua en lugar de discreta, y observe que la integral de 1/N es log N )

Su serie armónica es la fórmula de todo el algoritmo (como ha concluido correctamente)

Entonces, tu suma:

N + N/2 + N/3 + ... + N/N = N * (1 + 1/2 + 1/3 + ... + 1/N) = Theta(N * log N)

Entonces, el límite apretado para el algoritmo es N*log N

Ver la prueba matemática [rigurosa] aquí (ver la parte "Prueba integral" y "Velocidad de divergencia")

Answer 2

Bueno, puedes usar metódicamente la notación Sigma: