Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Java Help-Improving runtime complexity of the method

  1. Jan 6, 2017 #1
    Hello everyone,
    Looking for a more efficient solution to method 'what', in terms of run-time complexity and space.
    The method finds the largest cell sequence that the organs sum is divided by 3.(Correct me if I'm wrong)

    As it seems runtime complexity here is O(n ^ 3).
    I came to solution of O(n ^ 2), is there a more effective solution? Explain please,
    Thanks for the helpers !


    HrtOq9r.png NT6Oi4w.jpg
     
  2. jcsd
  3. Jan 6, 2017 #2

    jedishrfu

    Staff: Mentor

    It seems you are resumming things over and over in the f method

    f(a,0,3) means sum elements a[0..3]

    then you do f(a,0,4) which means sum elements a[0..4]

    why not remember the sum and just add a[4] to it?

    This will eliminate the innermost loop in the f method.
     
  4. Jan 6, 2017 #3

    jim mcnamara

    User Avatar

    Staff: Mentor

    As a good rule of thumb, correct algorithms have the potential to contribute the most to efficiency.

    If I understand what this code is supposed to do, I would consider a different algorithm - Kadane's maximum subarray algorithm.
    https://en.wikipedia.org/wiki/Maximum_subarray_problem
     
  5. Jan 6, 2017 #4

    jim mcnamara

    User Avatar

    Staff: Mentor

    Hmm - found this in my code store, made simple example in C
    Code (Text):

    #include <stdio.h>
    #include <stdlib.h>
    #include <limits.h>

    // Kadanes Algorithm  in C
    // Parameters:
    // a array of integers
    // sz number of elements in the array

    int max_sum_subarr(int *a, const size_t sz)
    {
        int i=0;
        int local_mx = INT_MIN;
        int mx_ending = 0;
        for (i = 0; i < sz; i++)
        {
            mx_ending = mx_ending + a[i];
            if (local_mx < mx_ending)
                local_mx = mx_ending;
            if (mx_ending < 0)
                mx_ending = 0;
        }
        return local_mx;
    }
    int main(int argc, char **argv)
    {
       size_t sz=7;
       int a[7]={1 , 4, -1, -7, 3, 2, 1 };
       
       printf("maximum sub array = %d\n", max_sum_subarr(a, sz) );
       
       return 0;
    }
     
    Note the complexity change.
     
  6. Jan 10, 2017 #5
    I need to find algorithm to method that return the size of largest sequence that his amounts divisible by 3, in O N complexity..
    for example, for array
    {0,0,1,1,1,1,1} the method return 5 . {0,0,1,1,1}
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Help-Improving runtime complexity of the method
  1. Help with a method (Replies: 3)

  2. Runtime libraries (Replies: 7)

  3. Help with the runtime (Replies: 0)

  4. Runtime error 112 (Replies: 3)

Loading...