首页 文章

凸壳算法的时间复杂度

提问于
浏览 次
2

凸包算法的复杂性可以用求和符号表示为：

1 C(n)=sum(i=1..n-1)sum(j=i+1..n)sum(k=1..n)1
2 =sum(i=1..n-1)sum(j=i+1..n)n
3 =nsum(i=1..n-1)sum(j=i+1..n)1
4 =nsum(i=1..n-1)(n-i)

从这里我的教授直接跳到：

5 =nsum(i=1..n-1)i
6 =n*n(n-1)/2
7 =(n^3-n^2)/2

我不知道他是如何摆脱第4行的n . 我尝试了一种不同的方法并得到了一个完全不同的答案：

5 =nsum(i=1..n-1)n - sum(i=1..n-1)i
6 =nsum(i=1..n-1)n - n(n-1)/2
7 =n^2sum(i=1..n-1)1 - n(n-1)/2
8 =n^2(n-1) - n(n-1)/2
9 =n^3-n^2 - n^2/2 - n/2

任何人都可以解释我的教授如何摆脱n以及为什么我的解决方案不正确？

谢谢

algorithm convex-hull

2 回答

  • 0

    扩展条款：

    nsum(i=1..n-1)(n-i) = (n-1) + (n-2) + ... + (n-(n-1))=1

    现在反过来看看它们：

    1 + ... (n-2) + (n-1) = sum(i=1..n-1)i
    回复于
  • 1

    要查看错误的位置，您需要做的就是为 n 选择一个小数字，并查看数学如何运作 . 所以让我们选择 n=3 .

    4 =3sum(i=1..2)(3-i) = 3(2+1) = 9
5 =3sum(i=1..2)i     = 3(1+2) = 9

    现在你的

    5 =3sum(i=1..2)3 - sum(i=1..2)i = 3(3+3) - (1+2) = 18-3 = 15

    问题是你没有将这两个术语乘以 n

    5 =n(sum(i=1..n-1)n - sum(i=1..n-1)i)
6 =n( (n-1)n - (n-1)n/2 ) 
7 =n( (n-1)n/2 )
    回复于

相关问题