weixin_43176170
2018-12-17 11:53
采纳率: 33.3%
浏览 1.3k

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

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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • blownewbee 2018-12-17 11:59
    已采纳

    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

    点赞 评论

相关推荐 更多相似问题