如何以递归形式编写算法并显示其运行时间 [英] How do I write an algorithm in recursive form and show its running time

问题描述

您好，



我被要求以递归形式写入伪代码Θ（n）-time算法，给定一组

n整数，确定S中哪两个元素的总和最大。



任何人都可以帮我解决这个问题并解释如何显示实际的运行时间通过解决复发问题？



谢谢



我尝试了什么：



我能够编写一个算法，如果集合已经排序，但我不允许使用排序数组，因为这将是Θ（n log n） -time

解决方案

O（n）表示你将遍历每个元素，所以如果你有10个元素你将通过所有10个元素来获得你的结果。



有了这个评论，你应该可以做你的家庭作业。

Hello,

I am asked to write in pseudocode a Θ(n)-time algorithm in recursive form that, given a set S of
n integers, determines which two elements in S have the largest sum.

Can anyone help me with this problem and explain how you can show the actual running time by solving the recurrence ?

Thank you

What I have tried:

I am able to write an algorithm if the set is sorted, but I am not allowed to use a sorted array as this would be Θ(n log n)-time

解决方案

O(n) means you will go through each element, so if you have 10 elements you will go through all 10 elements once to get your results.

With that comment you should be able to do your homework.

这篇关于如何以递归形式编写算法并显示其运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！