我是否正确计算了解决方案的时间复杂度？

Question

我一直在尝试通过在线学习和解决 leetcode 问题来更好地掌握数据结构和算法。我也在尝试了解如何计算我的算法的时间复杂度，以弄清楚如何改进它们。刚做完LeetCode题目：Third Maximum Number。我假设我的解决方案没有优化太多，因为它只比 45% 的解决方案快。但我认为它在线性 O(n) 时间内仍然是运行ning。这是我的代码：

我算对了吗？我的算法运行在 O(n) 中吗？感谢大家的帮助！

Answer 1

首先，毫无疑问，你算法的复杂度是O(n)。但是，这并不是您的代码的确切复杂性，您可以改进几个地方。这是列表：

set操作的复杂度是O(1)，但在更坏的情况下（当你在每次插入时都发生散列冲突）复杂度会提高到O(n)。因此，您的 list(set(nums)) 的总体复杂性可能是 O(n^2).
要找到第三大数，您运行 O(n) 循环三次。显然，Big-O 的表示法是 O(n) 但实际上你是运行ning 表示 3 * n.

你可以考虑在这方面进行改进。请记住，由于代码优化，具有相同 Big-O 复杂度的两个算法可能具有不同的实际运行时间。我进一步思考了这个问题，发现这个问题可以通过运行对 n 数字进行一次循环来解决。这是我的 C++ 代码：

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        const long long int MIN = ((long long int) 1 << 60) * (-1);
        int sz = nums.size();
        long long int mx1, mx2, mx3;
        mx1 = mx2 = mx3 = MIN;
        
        for(int n : nums) {
            if(mx1 <= n) {
                if(mx1 == n) continue;
                mx3 = mx2;
                mx2 = mx1;
                mx1 = n;
            }
            else if (mx2 <= n) {
                if(mx2 == n) continue;
                mx3 = mx2;
                mx2 = n;
            }
            else if (mx3 < n) mx3 = n;
        }
        
        if(mx3 == MIN || mx2 == MIN) return mx1;
        return mx3;
    }
};

这段代码的运行时间是4 ms，比这个问题的C++在线提交97.13%快

我是否正确计算了解决方案的时间复杂度？

Did I correctly calculate the time complexity of my solution?

algorithm

performance

time-complexity

data-structures