时间复杂度演习

Question

我在做一次运动时遇到了麻烦。上下文是对运行时间的渐近分析。给出了插入排序等算法，结果应该是输入{N，N-1，…，N/2，1，1，2，3，…，N/2}的θ表示法(渐近精确)。问题是:如何计算运行时间？我是说，算出最坏的或最好的情况都没问题。我的问题是如何处理输入，以及如何在计算中考虑它们。

谢谢你的帮忙!

问候GR

Answer 1

见评论：

你有没有试过列出一些简单输入的步骤，比如(4，3，2，1，1，2)或(6，5，4，3，1，1，2，3)？你能列出一般情况N的步骤吗？-大卫K 10月23日16:32

首先，谢谢你的回答。-)我只是简单地数一数所加的数，并作比较。所以在插入排序中有n(n-1)\2操作.在这种情况下，Theta是Theta(n*n)。我现在的问题是，我如何将它映射到一个真正的输入？- GR_ 10月23 '14在18:31

如果您实际上已经计算了插入排序的最坏情况复杂性的操作，那么您可以知道在第10次操作中比较了哪些数字来对数字1到100进行排序。也就是说，计数操作是将操作映射到实际输入。这实际上是一个更困难的问题，因为您还必须确定输入是最坏的情况，而这里已经为您描述了输入。-戴维·K( David K.)10月23日下午7:01