Строковый анализ алгоритма с ранним заявлением о возврате

Question

Я пытаюсь выполнить домашнюю работу для класса алгоритмов, и я столкнулся с ситуацией, которая не описана в книге. Моя задача - создать алгоритм и выполнить линейный анализ Sequential или Linear Search, чтобы найти элемент k в массиве A[p...r].

Мой алгоритм смешного прост:

1 for ct=1 to r 
2  if A[ct] == k 
3   return ct 
4 return -1 

Наглядно, я уже знаю, что этот алгоритм будет работать в Q (1) при оптимальных условиях и Q (п) при худшем случае, но я немного имеющий не удается выполнить линейный анализ, чтобы доказать это.

Вот то, что я до сих пор для моего анализа (обратите внимание, что #s рядом с константами и J под TJ должен быть подстрочный):

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 будет б e выполнил только один раз, поэтому я перечислил их как постоянное время, но на самом деле только один из них будет когда-либо выполняться во время поиска. Я знаю, что для асимптотических обозначений, что константы не имеют большого значения, но беспокоит, что мой оператор tj(c1+ c2) + (c1 + c3 + c4) включает в себя c3 + c4, потому что я знаю, что это действительно должно быть чем-то более похожим на c3 or c4.

Вопросы

Я могу подключить мой Т (п) соответственно, так что T (1) = Θ (1) и Т (п) = Θ (п), но я чувствую, что я точно не доказали это.

• Может кто-нибудь весить, где моя математика может быть неправильной?
• Как вы должны оценивать операторы раннего возвращения внутри алгоритма?

Answer 1

Я могу подключить мой Т (п) соответственно, так что T (1) = Θ (1) и Т (п) = Θ (п), но я чувствую, что у меня нет точно доказал это.

Может ли кто-нибудь весить, где моя математика может быть неправильной?

Я слишком поздно, и я уверен, что вы уже знаете, все это, но здесь идет:

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? 

Сложность идут от лучшего случая к худшему случаю (и в среднем случае), вы оценивающие худший случай. Ранний возврат вписывался в лучший случай. Там, где это предполагалось, это стало возможным.