Cześć . Właśnie napisałem algorytm w C# , który wypełnia „jodełką” tablicę kwadratową o wymiarze n.
Np. dla n równego 5, tablica ta jest postaci:
1 1 1 1 1
1 2 2 2 2
1 2 3 3 3
1 2 3 4 4
1 2 3 4 5
Muszę oszacować złożoność czasową mojego algorytmu , jednakże nie za bardzo pojmuje czy dobrze myślę byłbym bardzo wdzięczny za wskazówki jak i doradzenie w tej sprawie.
Operacja dominująca :
pętla for?
Funkcja złożoności (w najgorszym przypadku):
F(N)=O[(1+n)/2]*n=O[(n/2)+(n^2)/2]=O(n^2) - złożoność kwadratowa.
Rząd złożoności w najgorszym przypadku:
tutaj nie wiem?
Mam też pytanie czy jest jakiś program , który po wrzuceniu kodu wyrzuci mi wykres zależności czasu wypełnienia tablicy kwadratowej? Jeżeli nie to w jaki sposób mógłbym to zrobić?cheeky
Mój kod:
class Program
{
static void Main(string[] args)
{
int n = 8;
int[,] tab = new int[n, n]; //tworzenie tablicy kwadratowej o wymiarze n
int number = 1; //numer od jakiego zaczynamy wstawiać do tablicy
int index = 0; //index od ktorego wstawiamy do tablicy
for (int i = 0; i < n; i++) //pętla wstawiająca elementy
{
for (int j = index; j < n; j++)
{
tab[index, j] = number; //przypisywanie elementów
tab[j, index] = number; //przypisywanie elementów
}
index++; //zwiekszanie indexu
number++; //zwiekszanie liczby
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
Console.Write(tab[i, j]);
}
Console.WriteLine("");
}
}
}
