Am I doing this Time complexity for a while loop right?(在一段时间内，我做这个时间复杂性循环是正确的吗？)-6ren

Am I doing this Time complexity for a while loop right?(在一段时间内，我做这个时间复杂性循环是正确的吗？)

转载作者：bug小助手更新时间：2023-10-28 20:57:23

This is what I calculated, I find myself struggling when It comes to the while loops. Did I do this correctly?

这就是我的计算结果，我发现自己在While循环方面遇到了困难。我做得对吗？

                        //Cost      Times
    count = 0;          //c1        //1
    int j = N;          //c2        //1
    while(j>1) {        //c3        //log2(N) + 1
        count += 1;     //c4        //log2(N)
        j= j/2;         //c5        //log2(N)
    }//T(N) = c1*1 + c2*1 + c3* (log2(N)+1) + c4 * log2(N) + c5*log2(N) =
    //O(log2(N))

Please help me in anyway possible.

请尽一切可能帮我一下。

更多回答

The time complexity of the while loop is O(log2(n)). Not sure about your T(N) equation: I don’t think you include setup and assignments unless they have non-constant time complexities and pertain to the time complexity being assessed. But I haven’t done mathematical big-O analysis in quite some time.

While循环的时间复杂度为O(log2(N))。不确定你的T(N)方程式：我不认为你包括设置和赋值，除非它们具有非常定的时间复杂性，并且与正在评估的时间复杂性有关。但我已经有很长一段时间没有做过数学大O分析了。

Your thinking is too complicated. Write N as a binary number, composed of digits 0 and 1. j=j/2 is just shifting right. When the last digit 1 has vanished, the task is done. It's as easy as that.

你的想法太复杂了。写N为二进制数，由数字0和1组成。j=j/2只是右移。当最后一个数字1消失时，任务完成。就这么简单。

Just nitpicking: as the length of an int is limited, the complexity is O(1). ;-)

吹毛求疵：由于int的长度有限，复杂性为O(1)。；-)

Welcome to Stack Overflow! It's great to have you here. However, your question might benefit from some improvements. Could you provide more context and be more specific about your issue? This will help you get better responses. Please read following guide: How To: Write a good answer. Afterwards edit your post and improve it. Happy coding!

欢迎来到Stack Overflow！你能来真是太好了。但是，您的问题可能会因一些改进而受益。你能提供更多的背景，更具体地说明你的问题吗？这将帮助你得到更好的回应。请阅读以下指南：如何：写好答案。然后编辑你的帖子，并对其进行改进。编码快乐！

优秀答案推荐

Yes, your analysis is correct.

是的，你的分析是正确的。

Keep in mind though, when doing complexity analysis, normally you need a data set in order to establish a relationship between the data that is fed into an algorithm and the time needed to process it.

但是请记住，在进行复杂性分析时，通常需要一个数据集，以便在输入算法的数据和处理这些数据所需的时间之间建立关系。

For example, if your input is an array, the time complexity will indeed be O(logN) where N = the size of the array. (The logarithm base is typically ommited because it is assumed to be 2 in CS)

例如，如果您的输入是一个数组，那么时间复杂度实际上是O(LogN)，其中N=数组的大小。(通常省略对数底，因为在CS中假设它是2)

更多回答