c - 如何确定这些操作的复杂度？

Question

我已经使用这些日期结构实现了堆栈:

typedef struct node{
    StackEntry entry;
    struct node *next;
}Node;


typedef struct stack{
    Node *top;
}Stack;

如何找到下面每个操作的 BigO？

• StackEmpty(堆栈*s)

• 堆栈大小(堆栈*s)

• 推(节点 *e，堆栈 *s)

• 弹出(节点*e，堆栈*s)

Answer 1

时间复杂度

• StackEmpty(Stack *s) = O(1)//我们只需要检查 top== null或不

• StackSize(Stack *s) = O(n)//我们需要弹出 n 次 count++如果堆栈包含 n 个元素，则直到 top== null

• Push(Node *e, Stack *s) = O(1)//只需要一个操作，我认为不需要对此进行解释

• Pop(Node *e, Stack *s) = O(1)//只需要一个操作，我认为不需要对此进行解释

<小时/>

Boolean StackEmpty(Stack *s)

{
    if(s.Next==null&&s.value==null)
        return true; //or 1
    else
        return false; //or 0
}

int StackSize(Stack *s)
{
    if(StackEmpty!=true)
    {
        count = 0
        while(StackEmpty!=true)
        { 
           pop();
          Count++;
        }
     }
     return Count;
 }