Временная сложность алгоритма

@tut_ja · Регистрация: 17.04.2011

Студворк — интернет-сервис помощи студентам

Здравствуйте, форумчане

Возник такой вопрос: как найти минимальную и максимальную временную сложность алгоритма

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int i = 0; i < N - 1; i++)
                  {
                      for (int j = i + 1; j < N; j++)
                      {
                          if (Mas[i] > Mas[j]) 
                          {
                              int tmp = Mas[i];
                              Mas[i] = Mas[j];
                              Mas[j] = tmp;
                             
                          }
                     
                      }
                  }

я так понимаю временная сложность - это общее кол-во операций в алгоритме или нет?

@Killster · 04.06.2011, 17:21

О(n^2). (читается о-большое от эн в квадрате)
Где n - число элементов в массиве.

@chessman1 · 04.06.2011, 17:25

Сообщение от tut_ja

Здравствуйте, форумчане

Возник такой вопрос: как найти минимальную и максимальную временную сложность алгоритма

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int i = 0; i < N - 1; i++)
                  {
                      for (int j = i + 1; j < N; j++)
                      {
                          if (Mas[i] > Mas[j]) 
                          {
                              int tmp = Mas[i];
                              Mas[i] = Mas[j];
                              Mas[j] = tmp;
                             
                          }
                     
                      }
                  }

я так понимаю временная сложность - это общее кол-во операций в алгоритме или нет?

Вы для начала код откомпильте - не вдавался, но сразу вижу: код не работающий.

@Killster · 04.06.2011, 17:28

Сообщение от chessman1

Вы для начала код откомпильте - не вдавался, но сразу вижу: код не работающий.

Используется переменная N, это, очевидно, длина нашего масива минус один.. Скажем так, скорее всего

А алгоритм - пузырёк.

@tut_ja · 04.06.2011, 17:53 **[ТС]**

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int i = N - 1; i > 0; i--)
                  {
                      for (int j = 0; j < i; j++)
                      {
                          if (Mas[j] > Mas[j+1]) 
                          {
                              int tmp = Mas[j];
                              Mas[j] = Mas[j+1];
                              Mas[j+1] = tmp;
                             
                          }
                     
                      }
                  }

так лучше?

@chessman1 · 04.06.2011, 17:54

Сообщение от Killster

Используется переменная N, это, очевидно, длина нашего масива минус один.. Скажем так, скорее всего

А алгоритм - пузырёк.

А код то попробуйте откомпилировать.

@tut_ja · 04.06.2011, 18:01 **[ТС]**

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication1
{
    class Program
    {
        
        
        static void Main(string[] args)
        
        {
            Console.WriteLine("Geben Sie die Groesse von das Massiv");
            int N = int.Parse(Console.ReadLine());
            int[] Mas = new int[N];
            for (int i = 0; i < N; i++)
                {
                  Console.Clear();
                  Console.WriteLine("Geben Sie die Zahl von Massiv", i);
                  Mas[i] = int.Parse(Console.ReadLine());
                }
                  for (int i = N - 1; i > 0; i--)
                  {
                      for (int j = 0; j < i; j++)
                      {
                          if (Mas[j] > Mas[j+1]) 
                          {
                              int tmp = Mas[j];
                              Mas[j] = Mas[j+1];
                              Mas[j+1] = tmp;
                             
                          }
                     
                      }
                  }
 
                  Console.ReadLine();
                  Console.WriteLine("Fertig sortiert");
            for (int i = 0; i < N; i++)
                  {
                      Console.WriteLine(Mas[i]);
                  }
                  Console.ReadLine();
        }
    }
}

@chessman1 · 04.06.2011, 18:05

Сообщение от chessman1

А код то попробуйте откомпилировать.

Подсказываю: путь csc.exe program.cs

@Killster · 04.06.2011, 18:07

Сообщение от chessman1

А код то попробуйте откомпилировать.

У меня все ок о_О

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N = 10 ;
            Random r = new Random();
            int [ ] Mas = Enumerable.Repeat(0, N).Select(i => r.Next(0, 25)).ToArray(  ) ;
            Array.ForEach(Mas,i=>Console.Write(i+" "));
            Console.WriteLine( ) ;
            for (int i = 0; i < N - 1; i++)
            {
                for (int j = i + 1; j < N; j++)
                {
                    if (Mas[i] > Mas[j])
                    {
                        int tmp = Mas[i];
                        Mas[i] = Mas[j];
                        Mas[j] = tmp;
 
                    }
 
                }
            }
            Array.ForEach(Mas, i => Console.Write(i + " "));
            Console.WriteLine();
            Console.ReadLine( ) ;

@tut_ja · 04.06.2011, 18:27 **[ТС]**

например, если у нас число элементов n=5, то временная сложность О(5^2)=25?
как я понимаю, время выполнения программы пропорционально числу исполняемых операций, то есть 25 - это количество операций, выполняемых для упорядочивания 5 элементов?

@Killster · 04.06.2011, 18:29

tut_ja, Это - оценка сверху. Оценка снизу - O(n^2/2) вроде бы, если я прав.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@Killster 185 / 188 / 17 Регистрация: 26.11.2010 Сообщений: 511
	04.06.2011, 17:21
	О(n^2). (читается о-большое от эн в квадрате) Где n - число элементов в массиве. 0

@tut_ja 1 / 1 / 0 Регистрация: 17.04.2011 Сообщений: 24
	04.06.2011, 18:27 [ТС]
	например, если у нас число элементов n=5, то временная сложность О(5^2)=25? как я понимаю, время выполнения программы пропорционально числу исполняемых операций, то есть 25 - это количество операций, выполняемых для упорядочивания 5 элементов? 0

@Killster 185 / 188 / 17 Регистрация: 26.11.2010 Сообщений: 511
	04.06.2011, 18:29
	tut_ja, Это - оценка сверху. Оценка снизу - O(n^2/2) вроде бы, если я прав. 0