c# - 在n(log n)算法的末尾添加额外的循环是否会影响复杂性？

我写了一个算法来寻找数组中最长递增序列的长度。
该算法有一个包含序列的数组m，但在某些情况下，它不包含确切的序列。在这种情况下，我记录需要更改的索引和值。
这个算法是n（logn）
现在，为了找到实际的序列，我遍历数组m并替换另一个数组中记录的值如果N（log n），我的算法现在仍然有复杂性吗？
下面是C中的代码：

        int[] b = { 1, 8, 5, 3, 7, 2, 9 };

        int k = 1;

        int i = 1;
        int N = b.Length;

        List<int> m = new List<int>();
        int[] lup = new int[b.Length];

        m.Add(0);
        m.Add(b[0]);
        lup[0] = 0;
        while (i < N)
        {
            if (b[i] >= m[k])
            {
                k = k + 1;
                m.Add(b[i]);
            }
            else
            {
                if (b[i] < m[1])
                {
                    m[1] = b[i];
                }
                else
                {
                    int j;
                    j = Binary_Search(m, b[i], m.Count - 1);
                    //if the item to be replaced was not the last element, record it
                    if (m[j] > b[i] && j != k)
                    {
                        lup[j] = m[j];
                    }
                    m[j] = b[i];

                }
            }
            i = i + 1;

        }

        Console.WriteLine("The Input Sequence is : " + string.Join("\t", b));
        Console.WriteLine("Length of Longest Up Sequence is : " + k.ToString());

        List<int> result = new List<int>();

        // create result based on m and lup
        //DOES THIS LOOP EFFECT PERFORMANCE??
        for(int x = 1; x < m.Count; x++)
        {
            if (lup[x] == 0)
            {
                result.Add(m[x]);
            }
            else
            {
                result.Add(lup[x]);
            }
        }

最佳答案

你的直觉是正确的添加这个循环是n*（log（n）+1），所以它仍然是n*log（n）。