计算凸包的——Graham扫描法的时间复杂度为O（nlogn）具体是怎么来的？

Question

计算集合中，Graham扫描法的时间复杂度为O（nlogn），说的主要是根据排序的复杂度O（nlogn），想请问下这里的复杂度O（nlogn），具体是怎么算出来的？

Answer 1

https://blog.csdn.net/cumtwyc/article/details/49387333

核心算法是

    for(i = 3;i < n;i++){
        while(xmul(point[i],point[stack[top]],point[stack[top-1]]) >= 0){//弹出非左转的点
            if(top == 0) break;
            top--;
        }
        stack[++top] = i;
        }

外侧循环遍历N，内侧使用堆栈搜索顶点是LogN，所以是NLogN