时间戳

首页 > 解决方案 > 关于 3-Sum 算法，数组访问次数如何计算（1/2 N^3），增长顺序如何计算（N^3）？

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

问题描述

相关讲座幻灯片

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

标签： javaalgorithm

解决方案

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

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

推荐阅读