Results 1 to 17 of 17

Thread: computational time

  1. #1
    Join Date
    Jan 2006
    Posts
    976
    Thanks
    53
    Qt products
    Qt3
    Platforms
    Windows

    Default computational time

    Hello,
    could you suggest me any link where find information about algorithms that work in logarithmic and quadratic time. (And how to compute it) I'd like build the same alg and see the time different between them. Will it be possible have the same computation with this different two features?

    thanks.

    -- EDIT
    I think to order a list of numbers or other....
    Last edited by mickey; 26th October 2007 at 12:39.
    Regards

  2. #2
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    5,372
    Thanks
    28
    Thanked 976 Times in 912 Posts
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11 Windows

    Default Re: computational time

    Does logarithmic time mean O(log n) or maybe O(n log n) will be enough? Because in the latter case you can find good examples quite easily.

  3. #3
    Join Date
    Jan 2006
    Posts
    976
    Thanks
    53
    Qt products
    Qt3
    Platforms
    Windows

    Default Re: computational time

    Quote Originally Posted by jacek View Post
    Does logarithmic time mean O(log n) or maybe O(n log n) will be enough? Because in the latter case you can find good examples quite easily.
    Ok, I mean Olog(n) (but If you have some link with O(nlog(n)) I'll read it too)....
    Regards

  4. #4
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: computational time

    Lookup in a tree is log(n) with the base of the number of children each node has - thus log2(n) in a binary tree. Bubble sort is O(n^2), because it iterates n times over a table of up to n elements. Most sorting algorithms are O(nlogn).

  5. #5
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    5,372
    Thanks
    28
    Thanked 976 Times in 912 Posts
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11 Windows

    Default Re: computational time

    Quote Originally Posted by mickey View Post
    Ok, I mean Olog(n)
    If the efficient algorithm is O(log n), then usually it's hard to find an inefficient version than would be worse than O(n). Of course you can always try to spoil the implementation to make it O(n^2), but I don't think this is what you want.

  6. #6
    Join Date
    Jan 2006
    Posts
    976
    Thanks
    53
    Qt products
    Qt3
    Platforms
    Windows

    Default Re: computational time

    Sorry but I don't necessary sort the list: I must only find one element in the list in logn time!!!
    EDIT -- But in a sorting, Do I have logn time only with a tree??
    Last edited by mickey; 26th October 2007 at 16:47.
    Regards

  7. #7
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    5,372
    Thanks
    28
    Thanked 976 Times in 912 Posts
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11 Windows

    Default Re: computational time

    Quote Originally Posted by mickey View Post
    Sorry but I don't necessary sort the list: I must only find one element in the list in logn time!!!
    You can't find an element in a list in O(log n), but it's possible with trees or arrays.

    Quote Originally Posted by mickey View Post
    But in a sorting, Do I have logn time only with a tree??
    It takes O(nlog n) to sort elements using a tree. Only insertion, removal and look up operations are O(log n) in a tree.

  8. #8
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: computational time

    You can achieve O(logn) complexity in finding an element in a list. But the list has to be presorted first (which in itself of course is O(nlogn)) - then you can use binary search to find the item you need. So if you can presort the list (once), you can have O(logn) lookup (many times).

  9. #9
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    5,372
    Thanks
    28
    Thanked 976 Times in 912 Posts
    Qt products
    Qt3 Qt4
    Platforms
    Unix/X11 Windows

    Default Re: computational time

    Quote Originally Posted by wysota View Post
    You can achieve O(logn) complexity in finding an element in a list. But the list has to be presorted first (which in itself of course is O(nlogn)) - then you can use binary search to find the item you need.
    You can't use binary search on a list --- it doesn't allow random access.

  10. #10
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: computational time

    Depends what you call a list. QList allows random access, so does an array (and a list can be implemented using an array or a vector). A linked list doesn't support random access - that's obvious. An algorithm doesn't enforce implementation, so I wasn't talking about any specific container, just about the algorithm itself.

  11. #11
    Join Date
    Jan 2006
    Posts
    976
    Thanks
    53
    Qt products
    Qt3
    Platforms
    Windows

    Default Re: computational time

    Quote Originally Posted by wysota View Post
    You can achieve O(logn) complexity in finding an element in a list. But the list has to be presorted first (which in itself of course is O(nlogn)) - then you can use binary search to find the item you need. So if you can presort the list (once), you can have O(logn) lookup (many times).
    Do you mean with presorted "sort the list before search"? In that cas, Yes, I can do everything I like. But I'd like don't use QT, then I call "list" a vector. If I understand right, for the sort I can't do better than O(nlogn). Is it that? Anyway, it seems that using a vector I can't use a tree; maybe I need implement my own tree...
    Regards

  12. #12
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: computational time

    Quote Originally Posted by mickey View Post
    Do you mean with presorted "sort the list before search"?
    Correct.
    If I understand right, for the sort I can't do better than O(nlogn). Is it that?
    Correct again.
    Anyway, it seems that using a vector I can't use a tree; maybe I need implement my own tree...
    If you want to sort a list, you don't need a tree. If you want to sort a tree, you can have a tree-like structure that is always sorted like a heap or traverse the tree in a sorted order, like with Binary Search Tree. If you want to look up an element in the tree, it will take O(logn), provided that the tree is sorted (like the BST tree again). If you want even faster lookup, use a hashing table - the complexity of lookup is then O(1) with worst case of 'n' if all elements end up in a single node. You can also combine the hash table with a tree which will have the worst case of logn.

  13. #13
    Join Date
    Jan 2006
    Posts
    976
    Thanks
    53
    Qt products
    Qt3
    Platforms
    Windows

    Default Re: computational time

    1. I read some pages and I'm more confused now; I read that search in abinary-tree is O(n) (i.e. create a tree with this elements in input with this order: 10,20,30,40,50 -> O(5) = O(n).
    I read (If I understand right) that we can count on the fact that we can't always unlucky and than the input distribution, on average, can be better: for this reason we can have O(logn) (30,20,40,10,50) in in this order). Is it this?

    2. If I can obtain a search in OLogn(n) with an sorted array, for clearly, I prefer this....I guess it'll be the same of a sorted vector<int>
    Last edited by mickey; 27th October 2007 at 17:24.
    Regards

  14. #14
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: computational time

    Quote Originally Posted by mickey View Post
    1. I read some pages and I'm more confused now; I read that search in abinary-tree is O(n) (i.e. create a tree with this elements in input with this order: 10,20,30,40,50 -> O(5) = O(n).
    This is the worst case scenario for an unbalanced tree - in the above mentioned case your tree becomes a list. On average the complexity is O(logn) and balancing the tree (see AVL Trees) guarantees O(logn) lookup in the worst case too (the insertion is slower though).

    2. If I can obtain a search in OLogn(n) with an sorted array, for clearly, I prefer this....I guess it'll be the same of a sorted vector<int>
    Yes, a vector is also an array.

  15. #15
    Join Date
    Jan 2006
    Posts
    976
    Thanks
    53
    Qt products
    Qt3
    Platforms
    Windows

    Default Re: computational time

    what I don't still understand is:
    Qt Code:
    1. //pseudo code
    2. int a[5] = {10,20,30,40, 45}
    3. bool search (int a[5], int value) {
    4. for (int i=0; i< a.lenght; i++)
    5. if (value == a[i]) return true;
    6. return false;
    7. }
    8. search (45); -> this is what'll happen in the worst case. And it's O(n).......and array was sorted.....It isn't O(logN)
    To copy to clipboard, switch view to plain text mode 

  16. #16
    Join Date
    Feb 2006
    Location
    Romania
    Posts
    2,744
    Thanks
    8
    Thanked 541 Times in 521 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: computational time

    Quote Originally Posted by mickey View Post
    what I don't still understand is:
    Qt Code:
    1. search (45); -> this is what'll happen in the worst case. And it's O(n).......and array was sorted.....It isn't O(logN)
    To copy to clipboard, switch view to plain text mode 
    Yes, great analysis!
    It is O(n) because you searched in an array, not in a balanced binary tree and because you used the wrong searching algorithm.
    To get the time you want you have to use a O(logn) sort algorithm such as qsort to sort the array and then use binary search to find a value.

  17. #17
    Join Date
    Jan 2006
    Location
    Warsaw, Poland
    Posts
    33,359
    Thanks
    3
    Thanked 5,015 Times in 4,792 Posts
    Qt products
    Qt3 Qt4 Qt5 Qt/Embedded
    Platforms
    Unix/X11 Windows Android Maemo/MeeGo
    Wiki edits
    10

    Default Re: computational time

    The very basic implementation of binary search in an array is more or less like this:
    Qt Code:
    1. int a[5] = {10,20,30,40,45};
    2. int search(int *tab, int value, int low, int high){
    3. int med = low+(high-low)/2;
    4. if(tab[med]>value)
    5. return search(tab, value, low, med);
    6. else if(tab[med]<value)
    7. return search(tab, value, med, high);
    8. else if(tab[med]==value)
    9. return med;
    10. return -1;
    11. }
    To copy to clipboard, switch view to plain text mode 
    When you call it as search(tab, 45, 0, 4) it will compare to 30, then to 40 and then to 45. It requires three steps for a 5 item array, which is more or less O(logn).

Similar Threads

  1. time and date issues
    By boog07005 in forum Newbie
    Replies: 5
    Last Post: 20th August 2012, 16:15
  2. to set date and time in the file info of two days back
    By thomasjoy in forum Qt Programming
    Replies: 1
    Last Post: 11th October 2007, 17:54
  3. QDateTime GMT add sec. or - sec. from locale time....
    By patrik08 in forum Qt Programming
    Replies: 2
    Last Post: 20th February 2007, 17:39
  4. Compiling time changes, and how!
    By GreyGeek in forum Qt Programming
    Replies: 2
    Last Post: 2nd February 2006, 14:19
  5. Problem with pointers while using localtime() and time()
    By jamadagni in forum General Programming
    Replies: 7
    Last Post: 11th January 2006, 16:48

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.