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

@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) вроде бы, если я прав.

Новые блоги и статьи Все статьи Все блоги /
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .

@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