Capisco che puoi generare un algoritmo O (N ^ 2) usando i loop:
es:
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
//do something N^2 times.
}
}
È possibile generare un O (N ^ 2) senza usare loop (for, foreach, while, goto)? Come lo faresti?
Ecco un esempio un po 'forzato, quadrando un numero usando ricorsione e senza anelli.
using System;
public class Program
{
public static void Main()
{
var num_to_square = 10;
Console.WriteLine(square(num_to_square)); //100
}
public static int square(int n)
{
return recurse(n-1, n-1);
}
private static int recurse(int x, int y)
{
int c = 1;
if (x + y == 0)
{
return c;
}
c += recurse(x - 1, y);
if (x == y)
{
c += recurse(x - 1, y - 1);
}
return c;
}
}
No. * Qualsiasi algoritmo senza loop deve essere O(1) , perché sai al momento della compilazione quanti passi l'algoritmo richiederà (al massimo).
A meno che per "usare un loop" intendi effettivamente scrivere una delle istruzioni di iterazione C #: for , foreach , do o while . Poi ovviamente ci sono altri modi, ma direi che sono solo modi diversi di fare un ciclo. Ad esempio:
i = 0;
Outer:
j = 0;
Inner:
//do something N^2 times.
j++;
if (j < N) {
goto Inner;
}
i++;
if (i < N) {
goto Outer;
}
Questo è il tuo stesso ciclo scritto con goto . O che ne dici di questo:
Enumerable.Range(0, N).SelectMany(i =>
Enumerable.Range(0, N).Select(j => { /*do something N^2 times*/ })
).ToList();
C'è lo stesso ciclo usando Enumerable metodi ed estensioni. Conta se l'implementazione di ToList utilizza un ciclo?
* A seconda di come conti la ricorsione
Sicuramente c'è da sostenere che la ricorsione è semplicemente "diversa" dall'iterazione, ma ogni algoritmo ricorsivo può essere convertito in un equivalente iterativo. In effetti sarebbe perfettamente ragionevole per un compilatore farlo. Il tuo algoritmo "usa un ciclo" se è logicamente equivalente a un algoritmo che utilizza un ciclo? Dipende esattamente da cosa intendi per "algoritmo".