Java Stack array - Big O notation

Question

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

import java.util.*; 
import java.util.InputMismatchException; 
import javax.swing.*; 
public class MyStack { 

    private int maxSize; 
    private long[] stackArray; 
    private int top; 
    public MyStack(int s) { 
     maxSize = s; 
     stackArray = new long[maxSize]; 
     top = -1; 
    } 
    public void push(long j) { 
     stackArray[++top] = j; 
     System.out.println("Push onto stack"); 
    } 
    public long pop() { 
     return stackArray[top--]; 
    } 
    public long peek() { 
     return stackArray[top]; 
    } 
    public boolean isEmpty() { 
     return (top == -1); 
    } 
    public boolean isFull() { 
     return (top == maxSize - 1); 
    } 
    public static void main(String[] args) { 
     Scanner num = new Scanner(System.in); 
     int input =0; 
     int x; 
     MyStack theStack = new MyStack(5); 
    for(x=0; x<5; x++) 
    { 


     System.out.println("\nEnter a number(Push): "); 
     input = num.nextInt(); 
     theStack.push(input); 



     } 



    System.out.print("The first element on the top is the top of the stack"); 
    System.out.println(""); 
     while (!theStack.isEmpty()) { 
     long value = theStack.pop(); 
     System.out.print(value); 
     System.out.println(" Pop"); 

     } 


     System.out.println(""); 

    } 
} 

Answer 1

Характеристики Big O варьируются в зависимости от операции, которую вы пытаетесь выполнить. Посмотрите на свой метод isEmpty(). Он всегда просто смотрит на значение top, так что это константа, или O (1). Я не вижу других методов в вашем классе (кроме main(), которые мы рассмотрим через минуту), которые имеют какую-либо зависимость от количества элементов в массиве, все они работают только с вершиной.

main() просто запрашивает 5 значений, затем распечатывает их. Если бы он запросил 50, это потребовалось бы в десять раз дольше (при условии, что вход пользователя оставался относительно постоянным). Таким образом, основной является O (n), где n - количество элементов в массиве.

Если вы искали определенное число в массиве, вам, вероятно, придется проверять каждый по очереди, поэтому O (n).

И если вы делали что-то более сложное, когда вы смотрели на каждый элемент, а затем выполняли какую-либо операцию или сравнивали друг с другом (например, с вложенным циклом), вы попадали бы в O (n^2).

Надеюсь, что это поможет вашему мыслительному процессу.

Answer 2

Производительность всех ваших методов в O (1), поскольку они просто индексируют массив или проверяют значение верхнего уровня.

В теле основных для цикла выполняется 5 раз, выполняя 5 толчки, таким образом, O (5 * 1) = O (N), так как стек имеет размер п = 5.

После этого во время цикла вытащит стек до тех пор, пока он не станет пустым. Поскольку стек может содержать только 5 элементов (что также является его размером), это снова означает O (5 * 1) = O (n).

Итак, вы можете предположить, что оно находится в O (2 * n), которое дает O (n).

Answer 3

Сложность операции структуры данных всегда вычисляется против количества элементов, которые она удерживает, показывает максимальное время, которое потребуется с увеличением количества элементов.

Например: Сколько времени потребуется, чтобы найти элемент в «B-Tree», учитывая, что существует п число элементов, уже в нем.

В В-дерева времени поиска представляет собой О (§ п), означает, что максимальное время поиска будет расти как функция лог п (см Большой-О сложности график).

В вашем случае для реализации стека вы использовали массив, и у вас есть несколько отпечатков, но ваши операции не зависят от элемента, который несет ваш стек, поскольку сложность получения элемента в определенном месте - O (1). Таким образом, вся ваша операция занимает время O (1).

толчок - O (1)

поп - O (1)

isFull - O (1)

IsEmpty - O (1)

Но если реализовать поиск в ваш стек, проверьте, дано ли в вашем стеке длиннее, тогда поиск зависит от элементов, где вы должны перебирать все элементы, а сложность - O (n).