279. 完全平方数 时间效率为什么这么差呢

Question

我在leetcode上使用老师的方法，用最后的优化方案提交了C语言代码，但是运行效率却非常的低？对此我不太理解。
代码是这样的：

typedef struct node{
    int num;
    int dis;
} node;

int numSquares(int n){
    int front = 0, tail = 0;
    node queue[1000005] = {0};

    node nd = {n, 0};
    queue[tail++] = nd;
    
    int visited[n+1];
    memset(visited, 0, sizeof(visited));
    visited[n] = 1;
    while (front != tail) {
        node newNode = queue[front++];
        
        for(int i = 0; ; ++i) {
            int cal = newNode.num - i*i;
            if (cal < 0)
                break;
            if (cal == 0)
                return newNode.dis + 1;
            
            if(visited[cal] == 0){
                node next = {cal, newNode.dis+1};
                queue[tail++] = next;
                visited[cal] = 1;
            }
        }
    }
    return -1;
}

提交时间 提交结果 运行时间 内存消耗 语言
14 小时前 通过 288 ms 14 MB C
14 小时前 通过 252 ms 14 MB C

Answer 1

liuyubobobo 2020-11-18 13:41:51

如果把 node queue[1000005] = {0}; 的声明不放在函数内部，而作为全局变量，一下子就快了。理论上如过不用 node，而使用另外一个数组索引 num 对应的 dis 会更快一些。

但是这些非常语言相关的技巧不是课程的重点，同时，也和算法无关。甚至在很多时候，这些所谓的技巧是和好的编程模式相违背的。这就是为什么我不会再我的课程中强调这些“雕虫小技”的原因。通常在面试或者竞赛中，复杂度相同的算法，不管实现如何，是否使用这些“技巧”，都能通过；反之，通常阻止你 AC 一道题的瓶颈是算法的思路，而不是这些技巧。

继续加油！：）

• 提问者 MrZLeo #1

  觉得奇怪是因为算法的复杂度应该是一样的，而C语言实现理论上应该是非常快的，但是出来的结果却很奇怪，所以有点好奇 :D
  谢谢老师的解答！