该算法用于确定点是否在三角形内的时间复杂度（Big Oh、Omega 和 Theta）是多少？

Question

算法在python3中实现。它通过计算点和三角形不同坐标所形成的面积来判断一个点是否在三角形内。还有 better/faster 算法吗？

import math


#FUnction for calculating area
def CalcArea ( a1, b1, c1 ):
  a = CalcLength (a1, b1)
  b = CalcLength (a1, c1)
  c = CalcLength (b1, c1)
  s = ( a+b+c ) / 2
  return math.sqrt( s * (s-a) * (s-b) * (s-c) )

#Function for calculating length of line segment
def CalcLength ( a1, b1 ):
  return math.sqrt( ((b1[0]-a1[0])**2) + ((b1[1]-a1[1])**2)  )

#Main function to check if point is inside triangle based on areas
def TotalAreaChk ( a, b, c, p ):
  totalArea = CalcArea( a,b,p ) + CalcArea( a,c,p ) + CalcArea( b,c,p )
  TriangleArea = CalcArea( a, b, c )

  if totalArea > TriangleArea:
    print ("The point does not lies inside the triangle")
  else:
    print ("The point lies inside the triangle")

#Declaring the coords 

A = ( 1.0, 2.0 )
B = ( 2.0, 2.0 )
C = ( 1.5, 1.5 )
P = ( 1.5, 1.8 )

TotalAreaChk(A, B, C, P)

Answer 1

O(N) 表示法告诉我们执行算法所需的时间如何与其输入的大小 N 成比例。在这种情况下输入的大小是多少？你会如何缩放它？

例如，您可以概括您的算法以测试给定点是否在具有 N 个顶点的多边形内。那么问算法的运行时间如何随 N 缩放是有意义的。或者你可以概括为允许三角形或多边形存在于 d 维 space，然后你可能会问关于运行时间 O(d).

提示：如果你的算法的运行时间对于所有输入都是相同的，你会如何用 O(N) 表示法来描述它？

该算法用于确定点是否在三角形内的时间复杂度（Big Oh、Omega 和 Theta）是多少？

What is the time complexity ( Big Oh, Omega and Theta ) for this algorithm for deciding whether a point is inside a triangle?

python

algorithm

big-o