Определить сложность алгоритма
сомневаюсь в правильности определения сложности алгоритма, подскажите каковой она является:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using System.Diagnostics;
namespace лб1
{
class Program
{
static void Main(string[] args)
{
Stopwatch watch = new Stopwatch();
watch.Start();
int a = 10;
int b = 15;
int k = 4;
int m = 0;
for (int i = a; i <= b ; i++)
{
m = 0;
for (int j = 1; j <= i; j++)
{
if (i % j == 0)
{
m++;
}
}
if (m == k)
{
Console.WriteLine(i);
}
}
watch.Stop();
Console.WriteLine("Затраченное время на работу программы :" + watch.Elapsed);
Console.ReadLine();
}
}
}
Склоняюсь к квадратичной сложности
Ответы (1 шт):
Автор решения: Harry
→ Ссылка
У вас внешний цикл от a до b, и внутренний - от 1 до переменной внешнего цикла.
В этом случае нетрудно просто посчитать, что общее число операций во внутреннем цикле -
(b+a)*(b-a+1)/2
т.е. O(b^2 - a^2)
Просто если, например, брать всегда b = a + const, то получится O(b).