Reno.and.Rude
BAN USER- 0 Answers Bigātheta complexity class: Trouble determining class + # operations from code:
I have finished some code, which works as I would like it to. I'm not looking to change for better optimization (right now).
However, I have trouble with determining Big-theta complexity classes in code, even if it's not my own. I was hoping someone could help explain an easy way to determine Big-theta complexity classes and show that it's true through general equations.
Here's my sample code: (determine Big-theta complexity class for longestRun and evenSplitPoint)
- Reno.and.Rude January 31, 2013import java.util.*; /** * Contains two methods for manipulating integer sequences in an array. * * @author Jonathan Jenkins * @version 1.0 * */ public class Algorithms1 { /** * Returns the value that appears in the longest run of consecutive values. * * @param list array containing int values to be processed * @return the value that appears in the longest "run" of consecutive values * */ public static int longestRun (int[] list) { /** @param num Initializing the first element of the array @param current Counting the first entry of the value count in the sequence to 1 @param max Initialize max to 1; keeps the max sequence @param value Will hold the value of the element that has the longest sequence and return it */ int num = list[0]; int current = 1; int max = 1; int value = 0; /** Traverse the array */ for (int i = 1; i < list.length; i++) { /** If the next element in the array is the same as the last element, incrase the current sequence by 1 */ if (list[i] == num) { current++; } /** Reset the current sequence to 1 since the next element in the array is not the same as the last */ else { current = 1; } /** If current sequence is greater than a previously max sequence, make the current sequence the new max sequence and store that element in value */ if (current > max) { max = current; value = list[i]; } /** Loads the next element of the array to be compared to the last */ num = list[i]; } /** @return Returns the element of the array that had the longest sequential sequence */ return value; } /** * * Returns the index of the value that would logically partition the array * into two sections, such that the sum of the values in each section is as * close to the other one as possible. * * @param list array containing int values to be processed * @return an index k, such that the sum of values 0..k and k+1..n-1 are as close as possible * */ public static int evenSplitPoint (int[] list) { /** @param total Initialize total */ int total = 0; /** For loop to compute the total of the entire array */ for (int i = 0; i < list.length; i++) { total += list[i]; } /** @param min The storage value for the smallest difference in left and right arrays; set to largest value in beginning @param equilibrium Initialize to store the index of the split point @param left The total value of the left side of the array @param right Currently the total of the array, later to be the total of the right side of the array */ int min = Integer.MAX_VALUE; int equilibrium = 0; int left = 0; int right = total; /** Traverse array */ for (int i = 0; i < list.length; i++) { /** Getting the sum of the left side of the array by adding elements to an empty total (0) */ left += list[i]; /** Gett the sum of the right side of the array by removing elements from a total sum */ right -= list[i]; /** Calculating the difference in the left and right arrays */ int diff = Math.abs(left - right); /** When the difference in the left and right arrays is less than the vaule stored in 'min', the equilibrium will be set to the current index and the difference will be the new 'min' */ if (diff < min) { equilibrium = i; min = diff; } } /** @return Returns the index at which the difference between the left and right arrays was the smallest */ return equilibrium; } public static void main(String[] args) { int[] a1 = {0, 2, 8, 8, 4, 4, 4, 8}; int[] a2 = {0, 0, 0, 0, 3, 3, 3, 8, 14, 21, 3, 3, 3}; System.out.println(longestRun(a1)); // 4 expected System.out.println(longestRun(a2)); // 0 expected System.out.println(evenSplitPoint(a1)); // 3 expected System.out.println(evenSplitPoint(a2)); // 8 expected } }
| Flag | PURGE