我正在为算法课做一些家庭作业，我遇到了书中没有描述的情况。我的任务是创建一个算法并对Sequential或Linear Search执行逐行分析，以查找数组k中的元素A[p...r]。
我的算法非常简单：
1 for ct=1 to r
2 if A[ct] == k
3 return ct
4 return -1
直观地说，我已经知道这个算法在最优情况下会在Θ（1）中执行，在最坏情况下会在Θ（n）中执行，但是我在执行逐行分析来证明这一点时遇到了一些困难。
这是我到目前为止的分析结果（请注意，常数旁边的#和tj下面的j应该是下标）：
Line | Algorithm | constants | time
1 for ct=1 to r c1 tj+1
2 if A[ct] = k c2 tj
3 return ct c3 1
4 return -1 c4 1
用它们的复杂性把常数加起来给我：
c1(tj+1) + c2tj +c3 + c4 = tj(c1+ c2) + (c1 + c3 + c4) = tj(c) + c = tj
这就是让我绊倒的…
在所有情况下，第3行和第4行只执行一次，这就是为什么我将它们列为常量时间，但实际上在搜索期间只执行其中一行我知道，对于渐近表示法来说，常数并不重要，但我的
tj(c1+ c2) + (c1 + c3 + c4)语句包含c3 + c4很麻烦，因为我知道它应该更像c3 or c4。问题
我可以适当地插入T（n），使T（1）=Θ（1）和T（n）=Θ（n），但我觉得我没有准确地证明这一点。
有人能指出我的数学哪里可能不正确吗？
如何在算法中计算早期返回语句？
最佳答案
我可以适当地插入T（n），使T（1）=Θ（1）和T（n）=Θ（n），但我觉得我没有准确地证明这一点。
有人能指出我的数学哪里可能不正确吗？
我来不及了，我敢肯定你已经知道了，但是现在：c1(tj+1) + c2tj +c3 + c4 = tj(c1+ c2) + (c1 + c3 + c4) = tj(c) + c = tj
我会改成c1(tj+1) + c2tj +c3 + c4 = tj(c1+ c2) + (c1 + MAX(c3,c4)) = tj(c) + c = tj
正如你指出的，只有C3或C4会运行，所以对于最坏的情况，我们选择一个更复杂的（尽管在这种情况下都是常数）。
How are you supposed to evaluate early return statements within an algorithm?
复杂度从最好的情况到最坏的情况（平均情况），你在评估最坏的情况。最好是早点回来如果条件允许的话。
关于java - 具有提前返回语句的算法的逐行分析，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26074754/