翻訳と辞書 Words near each other ・ 3RR ・ 3RRR ・ 3S ・ 3S Cable Car ・ 3S Understanding ・ 3sat ・ 3scale ・ 3Server ・ 3SH ・ 3SixtyMedia ・ 3SL ・ 3SPH ・ 3SR FM ・ 3Station ・ 3Steps ・ 3SUM ・ 3T ・ 3T (disambiguation) ・ 3T Cycling ・ 3T3 cells ・ 3T3-L1 ・ 3tera ・ 3TR FM ・ 3TU ・ 3U ・ 3V ・ 3V (payment system) ・ 3v3 Soccer ・ 3VOOR12 ・ 3W Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 3SUM ： ウィキペディア英語版 3SUM In computational complexity theory, the 3SUM problem asks if a given set of $n$ real numbers contains three elements that sum to zero. A generalized version, rSUM, asks the same question of ''r'' numbers. 3SUM can be easily solved in $O(n^2)$ time, and matching $\backslash Omega(n^)$ lower bounds are known in some specialized models of computation . It was widely conjectured that any deterministic algorithm for the 3SUM requires $\backslash Omega(n^2)$ time. In 2014, the original 3SUM conjecture was refuted by Allan Grønlund and Seth Pettie who gave a deterministic algorithm that solves 3SUM in time $O(n^2\; /\; (\; /\; )^)$. It is still conjectured that 3SUM is unsolvable in $O(n^)$ expected time.〔 When the elements are integers in the range $(\backslash dots,\; N)$, 3SUM can be solved in $O(n\; +\; N\backslash log\; N)$ time by representing the input set $S$ as a bit vector, computing the set $S+S$ of all pairwise sums as a discrete convolution using the Fast Fourier transform, and finally comparing this set to $-S$. ==Quadratic algorithm== Suppose the input array is $S()$. 3SUM can be solved in $O(n^2)$ time on average by inserting each number $S()$ into a hash table, and then for each index $i$ and $j$, checking whether the hash table contains the integer $-(S()+S())$. Alternatively, the algorithm below first sorts the input array and then tests all possible pairs in a careful order that avoids the need to binary search for the pairs in the sorted list, achieving worst-case $O(n^2)$ time, as follows.〔(Visibility Graphs and 3-Sum ) by Michael Hoffmann〕 sort(S); for i=0 to n-3 do a = S(); start = i+1; end = n-1; while (start < end) do b = S(); c = S(); if (a+b+c == 0) then output a, b, c; // Continue search for all triplet combinations summing to zero. start = start + 1 end = end - 1 else if (a+b+c > 0) then end = end - 1; else start = start + 1; end end end The following example shows this algorithm's execution on a small sorted array. Current values of a are shown in green, values of b and c are shown in red. -25 -10 -7 -3 2 4 8 10 (a+b+c==-25) -25 -10 -7 -3 2 4 8 10 (a+b+c==-22) . . . -25 -10 -7 -3 2 4 8 10 (a+b+c==-7) -25 -10 -7 -3 2 4 8 10 (a+b+c==-7) -25 -10 -7 -3 2 4 8 10 (a+b+c==-3) -25 -10 -7 -3 2 4 8 10 (a+b+c==2) -25 -10 -7 -3 2 4 8 10 (a+b+c==0) The correctness of the algorithm can be seen as follows. Suppose we have a solution a + b + c = 0. Since the pointers only move in one direction, we can run the algorithm until the leftmost pointer points to a. Run the algorithm until either one of the remaining pointers points to b or c, whichever occurs first. Then the algorithm will run until the last pointer points to the remaining term, giving the affirmative solution. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「3SUM」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.