c# - 如何使这个函数在恒定时间内处理？

Question

我需要找到这个无限级数的第 n 项：1,2,2,3,3,3,4,4,4,4...

你能给我这个任务的常数时间函数吗？

int i = 1;
while(true)
{
   if(i = n)
      //do things and exit the loop

   i++;
}

我认为这不会是一个恒定的时间函数......

Answer 1

编辑

阅读更多评论后，我似乎误解了这个问题。

如果您想在常数时间内找到数组n中第 th 位置的项目，那么答案很简单：，因为数组访问是常数时间。但是，如果由于某种原因您使用了一些访问时间不固定的容器（例如链表），或者不想在数组中查找值，则必须使用算术级数公式来找到答案。x[n]

算术级数告诉我们第 th 个独特项目的位置n将i是

n = i * (i - 1) / 2

所以我们只需要解决i. 使用二次公式，并丢弃无意义的否定选项，我们得到：

i = Math.Floor( (1 + Math.Sqrt(1 + 8 * n)) / 2)

原始回复

我假设您正在寻找第 n 个唯一项的位置，因为否则问题很简单。

听起来第 n 个唯一项的第一次出现应该遵循算术级数。即第 n 个唯一项的位置是：

n * (n - 1) / 2

Answer 2

鉴于我对这个问题的理解，这更像是一个数学问题而不是编程问题。

如果问题是：

给定一个由 1 的 1 个副本、2 的 2 个副本、3 的 3 个副本... n 个 n 的副本组成的无限序列，这个序列中的第 k 个值是多少？

现在处理这个问题的第一个线索是在第一次出现 n + 1 之前有 1 + 2 + 3... + n 个值。具体来说，在 n+1 之前有（前 n 个数字的总和）值，或者(n)(n-1)/2。

现在设置 (n)(n-1)/2 = k。乘以并有理化为 n^2 - n - 2k = 0。使用二次方程求解，得到 n = (1 + sqrt(1+8k))/2。它的下限为您提供了 n 之前有多少完整副本，并且令人高兴的是，给定基于零的索引，下限为您提供数组中第 k 个点的值。

这意味着您在 c# 中的最终答案是

return (int) Math.Floor((1 + Math.Sqrt(1 + 8 * k)) / 2);

给定非零基索引，

return (int) Math.Floor((1 + Math.Sqrt(-7 + 8 * k)) / 2);

Answer 3

        public static long Foo(long index)
        {
            if (index < 0)
            {
                throw new IndexOutOfRangeException();
            }

            long nowNum = 0;
            long nowIndex = 0;
            do
            {
                nowIndex += nowNum;
                nowNum++;
            } while (nowIndex < index);
            return nowNum;
        }