关于3-Sum算法，数组访问次数（1/2 N^3）如何计算，增长阶数（N^3）如何计算？

Question

我理解如何通过组合找到值 1/6 N^3，但我认为这代表了数组访问的次数。这张幻灯片说实际数字是 1/2 N^3。我知道我们只计算程序的数组访问次数，并且每次数组访问都是 1 个时间单位，但我不清楚波浪号表示法，以及如何从增长顺序的值中删除 1/2。有人可以解释一下吗？

Answer 1

该if语句被执行了1/6*N^3次。该语句的每次调用if都会导致 3 次数组访问：a[i]、a[j]、a[k]。所以我们得到：

(1/6*N^3) * 3 = 1/2*N^3