Определить сложность алгоритма программы
не могу правильно выявить сложность алгоритма программы. Программа составляет наибольшее возможное число из десятичных разрядов, цифры задаются пользователем.
using System;
namespace lb3
{
class Program
{
public static int index;
static void Main(string[] args)
{
Console.WriteLine("Введите строку");
string data = Console.ReadLine();
char[] mas = data.ToCharArray();
char[] result = new char[mas.Length];
int i = 0;
while (i < mas.Length)
{
result[i] = Search(mas);
mas[index] = ' ';
i++;
}
i = 0;
while (i < result.Length)
{
Console.Write(result[i]);
i++;
}
}
static char Search(char[] d)
{
int i = 1;
char max = d[0];
index = 0;
while (i < d.Length)
{
if (d[i] != ' ')
{
if (d[i] > max)
{
max = d[i];
index = i;
}
i++;
}
else
{
i++;
}
}
return max;
}
}
}
Ответы (1 шт):
Автор решения: Aziz Umarov
→ Ссылка
Ответ сложность О(n^2)
while (i < mas.Length) дает О(n)
while (i < mas.Length) { result[i] = Search(mas);// без учета mas[index] = ' '; i++; }Search() c while дает О(n)
while (i < d.Length) { if (d[i] != ' ') { if (d[i] > max) { max = d[i]; index = i; } i++; } else { i++; } }итого получается О(n^2)
while (i < mas.Length) { result[i] = Search(mas); mas[index] = ' '; i++; }
PS цикл
while (i < result.Length)
{
Console.Write(result[i]);
i++;
}
можно пренебреч поскольку O(n) намного лучше и он не будет влиять сильно на окончательную оценку