3.5.5 算法分析
对n个点进行排序需要O(n log n)的时间，这部分将会在第4章描述。在该算法的其余部分，for循环运行n次，但是内嵌的while循环会运行多少次呢？只要有左拐，那么就要把点从凸包中删除掉，直到剩下最初的三个点为止。由于凸包最多只会有n个点，因此这个while循环最多运行n次。于是，while循环的时间约为O(n)。综上所述，整个算法的时间复杂度是O(n log n)，因为排序的时间复杂度最大。
对n个点进行排序需要O(n log n)的时间，这部分将会在第4章描述。在该算法的其余部分，for循环运行n次，但是内嵌的while循环会运行多少次呢？只要有左拐，那么就要把点从凸包中删除掉，直到剩下最初的三个点为止。由于凸包最多只会有n个点，因此这个while循环最多运行n次。于是，while循环的时间约为O(n)。综上所述，整个算法的时间复杂度是O(n log n)，因为排序的时间复杂度最大。
