Confouse о Big-O нотации для этого исходного кода

Question

Может ли кто-нибудь помочь мне подсчитать алгоритмическую сложность моего исходного кода, используя обозначение Big-O? Эта программа предназначена для помещения NIM(студенческого идентификационного номера) в стек. Я до сих пор не знаю, как считать это особенно в if else, а также for, И это switch case функция сложность O(1)? Я просто новый программист. И мой лектор не дал четкого объяснения этому материалу. Пожалуйста, помогите мне Спасибо

#include <stdio.h>
#define MAX 800
int top;

//PUSH function
void push (int stack [], int item)
{   
 if (top == (MAX-1))
  printf("\nStack is empty\n");
    else
    {   
  ++top;
  stack [top] = item;
    }
}

//POP function
int pop (int stack[])
{  
 int ret;

    if (top == -1)
    {
  ret = 0;
    } else {

  ret = stack [top];
  --top;
    }

 return;
}

//Display function
void display (int stack[])
{   int i;

    if (top == -1){

     printf ("\nStack is empty\n\n");
    } else {   

  for (i=top; i>=0; --i)
     printf ("Value = %3d \n", stack[i]);
     printf("________________________________\n");
    }
    printf ("\n");
}

//Main Program
int main()
{  
 int stack[MAX], item;
    int choice;

    top = -1;

     do
 {
  do
  {
   printf ("___Main Menu___\n");
   printf ("1.Enter NIM\n");
   printf ("2.Delete NIM from top\n");
   printf ("3.How to use\n");
   printf ("4.Exit\n");
   printf ("Choice: ");
   scanf  ("%d", &choice);

     if (choice<1 || choice>3)
        printf ("\nYour choice is wrong. Please input 1-3!.\n\n");

  } while (choice<1 || choice>3);

    switch (choice)
    {
     case 1:
     printf ("\nEntered value : ");
     scanf  ("%d", &item);

     push (stack, item);

     display (stack);

     break;

    case 2:
     item = pop (stack);

     if(item == 0){

       printf("\nStack is empty\n\n");
     } else {

       display (stack);
     }

 break;

  case 3:
  printf("\nThis is a program to input NIM\n");
  printf("for the answer sheet");

  default:
     printf ("\nThanks for using this program :)");
          }
    } while(choice != 3);

 return 0;
}

Answer 1

Сложность алгоритма - это мера того, как время выполнения алгоритма изменяется в зависимости от его входного размера, когда этот входной размер становится большим. Поскольку мы заботимся только о том, когда входной размер становится большим, а точные константы времени выполнения будут различаться на разных платформах, мы рассматриваем только ведущие термины и игнорируем константы. Поскольку мы измеряем, как изменяется время выполнения алгоритма с его входными данными, нам необходимо определить, какой у нас ввод. Нет смысла измерять это для main, поскольку его время выполнения зависит от точного ввода, давая очень разное поведение для разных входных данных. Было бы целесообразно взглянуть на сложность push, pop, а также display по отдельности. Я буду только смотреть на display функция, оставляя других для вас, как учебное упражнение.

top == -1 операторы check и print выполняются в одно и то же время независимо от размера стека. В случае, если эта проверка не удалась (что происходит для непустого стека), тогда тело for цикл запускается один раз для каждого элемента стека. Доступ к элементу стека из памяти и печать его значения требует постоянного времени. Принимая n за размер стека, время выполнения T(n) определяется как (приблизительно) c1 + c2 * n, где c1 и c2 - это константы, которые зависят от вашей платформы. В обозначениях big-O O(c1 + c2 * n) = O(n).