三元搜索算法的时间复杂度 [英] Time Complexity of Ternary Search Algorithm

问题描述

我有一个作业，要我编写三元搜索算法，然后计算其时间复杂度。我能够为此编写一个算法，但无法提出任何计算复杂度的想法。我想我不明白大θ表示法的概念。

I have an assignment that wants me to write an ternary search algorithm and compute its time complexity afterwards. I was able to write an algorithm for it but I couldn't come up with any ideas how to compute its complexity. I think I didn't understand the concept of big-theta notation.

这是我的代码：它的工作方式类似于二进制搜索，但仅将列表分成多个部分并继续

Here is my code: It works like binary search but only divides the list into there pieces and continues the search like that.

    *some list which contains n increasingly-ordered integers;*

    int num;

    int min = 1;
    int max = n;

    int middle1 = (2*min+max)/3; 
    int middle2 = (min+2*max)/3;

    cin >> num;    //num is the number that is wanted to be found

    while (middle1 != middle2)
    {
        middle1 = (2*min+max)/3;
        middle2 = (min+2*max)/3;

        if(num <= list[middle1])
            max = middle1;
        else if(num >list[middle1] && num <= list[middle2])
            {
                    min= middle1; 
                    max = middle2;
            }
        else
            min = middle2;
    }
    if(num == list[max])
        cout << "your number is found in the "<< max <<"th location\n";
    else
        cout << "number cannot be found";

如果您可以用大θ表示法解释如何确定其复杂性，那将是非常

If you could explain how to determine its complexity in terms of big-theta notation, it would be very helpful for me.

推荐答案

在每一步中，您都在将可搜索范围的大小减小一个常数（在这种情况下， 3）。如果您在 n 步骤之后找到了元素，则可搜索范围的大小为 N   =  3 ⁿ 。相反，找到元素之前需要执行的步骤数就是集合大小的对数。也就是说，运行时为O（log N ）。进一步思考表明，您还可以始终构造需要所有这些步骤的情况，因此，最坏情况下的运行时实际上是Θ（log N ）。

At each step, you are reducing the size of the searchable range by a constant factor (in this case 3). If you find your element after n steps, then the searchable range has size N = 3ⁿ. Inversely, the number of steps that you need until you find the element is the logarithm of the size of the collection. That is, the runtime is O(log N). A little further thought shows that you can also always construct situations where you need all those steps, so the worst-case runtime is actually Θ(log N).

这篇关于三元搜索算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！