Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
darksiders150
0 / 0 / 0
Регистрация: 24.10.2017
Сообщений: 7
1

Получить аналитическую оценку трудоемкости работы алгоритма сортировки

26.03.2018, 06:36. Просмотров 374. Ответов 5
Метки нет (Все метки)

есть код программы и нужно вычислить трудоемкость алгоритма, а то какая-то шляпа получилась.
Pascal
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
program Project1;
 
const
  StSizeMax = 10000;
 
type
  TStack = record
    Pnt : Integer;
    Data : array[1..StSizeMax] of Integer;
  end;
    var
    ch:int64;
function Push(var aStack : TStack; const aNum : Integer) : Boolean;  //7
begin
  Push := False;  //1
  ch:=ch+1;
  with aStack do begin
    if Pnt < High(Data) then begin  //2
      Inc(Pnt);  //1
      Data[Pnt] := aNum; //2
      Push := True; //1
      ch:=ch+6;
    end;
  end;
end;
 
function Pop(var aStack : TStack; var aNum : Integer) : Boolean;  //8
begin
  Pop := False; //1
  ch:=ch+1;
  with aStack do begin
    if Pnt >= Low(Data) then begin //3
      aNum := Data[Pnt]; //2
      Dec(Pnt); //1
      Pop := True; //1
      ch:=ch+7;
    end;
  end;
end;
 
 
 
var
  St1, St2 : TStack;
  i, j, k,m, Num1, Num2 : Integer;
  F : Boolean;
begin
ch:=0; //1
  St1.Pnt := 0;    //1
  St2.Pnt := 0;    //1
  writeln ('введите количество элементов');
  readln(m); //1
  Randomize;   //1
  for i := 1 to M do Push(St1, Random(20)); //2
  ch:=ch+7;
 
  Writeln('Содержимое первого стека:');
  while Pop(St1, Num1) do begin // 8
    Push(St2, Num1); //7
    Writeln(Num1);
    ch:=ch+1;
  end;
  while Pop(St2, Num1) do Push(St1, Num1); //7+8
  ch:=ch+1;
  j := M;   //1
  ch:=ch+1;
  repeat
    F := False;  //1
    Dec(j);    //1
    ch:=ch+2;
 
    Pop(St1, Num1); //7
    for k := 1 to j do begin //1
    ch:=ch+1;
      Pop(St1, Num2);  //7
      if Num1 <= Num2 then begin   //2
        Push(St2, Num1); //8
        Num1 := Num2;  //1
        ch:=ch+3;
      end else begin   //1
        Push(St2, Num2);   //8
        F := True;   //1
        ch:=ch+2;
      end;
    end;
 
    Push(St1, Num1);  //8
    while Pop(St2, Num1) do Push(St1, Num1); //7+8
  until not F;
  ch:=ch+2;
 
  Writeln('Содержимое первого стека после сортировки:');
  while Pop(St1, Num1) do Writeln(Num1);    //7+8
  ch:=ch+1;
   Writeln('количество операций со стеком',' ',ch);
 
  Readln;
end.
Добавлено через 41 минуту
в примере реализации с очередью F(n)=17-3n-35n^2+12n^3+10n^4 ...у самого при разборе алгоритма вышло 42n^2+35n+27,но думаю это не правильно и нормальной литературы не нашел
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2018, 06:36
Ответы с готовыми решениями:

Время работы алгоритма пирамидальной сортировки массива
Чему равно время работы алгоритма пирамидальной сортировки массива A длины n, в...

Выбор алгоритма сортировки строк!
Дан массив строк. Каждый элемент массива содержит одно слово. Отсортировать...

Доказательство корректности алгоритма сортировки вставкой
В учебнике дается доказательство алгоритма вставки через математическую...

Определение времени работы алгоритма
Помогите надо определить время работы алгоримта Boolean: Function (integer:...

Как найти время работы алгоритма?
Пусть время работы алгоритма Т(N) = O(f(N)). Если X элементов обрабатываются за...

5
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,413
26.03.2018, 14:52 2
Цитата Сообщение от darksiders150 Посмотреть сообщение
ch:=ch+3;
Выглядит очень странно. Здравый смысл подсказывает, что 'количество операций со стеком' - это сколько раз мы вызывали Push или Pop.
0
darksiders150
0 / 0 / 0
Регистрация: 24.10.2017
Сообщений: 7
26.03.2018, 16:35  [ТС] 3
да знакомый скинул свою программу работы с очередью где демонстрировался счетчик по тому примеру и разбирался
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,413
26.03.2018, 22:16 4
Почему стек не реализуется в виде отдельной структуры данных?

Зачем пихать в одну функцию и ввод, и вывод, и сортировку?
0
darksiders150
0 / 0 / 0
Регистрация: 24.10.2017
Сообщений: 7
26.03.2018, 23:23  [ТС] 5
по другому не вышло организовать сортировку используя функции pop и push
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,413
27.03.2018, 10:20 6
Цитата Сообщение от darksiders150 Посмотреть сообщение
по другому не вышло организовать сортировку используя функции pop и push
Всё можно.
TStack вынести в отдельный файл. Вместо array[1..StSizeMax] использовать динамический массив.
Сортировку (строки 65-89) вынести в отдельную функцию.
0
27.03.2018, 10:20
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.03.2018, 10:20

Оценка трудоемкости алгоритмов
Здравствуйте. Поясните пожалуйста. Вот есть: Вычисление суммы S элементов...

Как найти время работы алгоритма, по заданным значениям?
Я чисто эмпирически понимаю, что время будет расти пропорционально квадрату...

Как найти время работы алгоритма, по заданным значениям?
Помогите пожалуйста найти время работы: Пусть время работы алгоритма Т(N) =...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru