Go to Post Chit Chat is frivilous but CD would be a colder place without it. - Koko Ed [more]
Home
Go Back   Chief Delphi > Technical > Programming
CD-Media   CD-Spy  
portal register members calendar search Today's Posts Mark Forums Read FAQ rules

 
 
 
Thread Tools Rate Thread Display Modes
Prev Previous Post   Next Post Next
  #2   Spotlight this post!  
Unread 30-07-2012, 20:21
BigJ BigJ is offline
Registered User
AKA: Josh P.
FRC #1675 (Ultimate Protection Squad)
Team Role: Engineer
 
Join Date: Jan 2007
Rookie Year: 2007
Location: Milwaukee, WI
Posts: 947
BigJ has a reputation beyond reputeBigJ has a reputation beyond reputeBigJ has a reputation beyond reputeBigJ has a reputation beyond reputeBigJ has a reputation beyond reputeBigJ has a reputation beyond reputeBigJ has a reputation beyond reputeBigJ has a reputation beyond reputeBigJ has a reputation beyond reputeBigJ has a reputation beyond reputeBigJ has a reputation beyond repute
Re: Replacing duplicates in a randomly generated array

This is a good example of time complexity.

The obvious easy way to "eliminate duplicates" is to just check each number you've picked so far, and if it is equivalent to your current number, skip it!

However, if this was for very large numbers it would not be good because it would have O(n^2) ("Big-O of n squared") time complexity. It would have to do a set of instructions for all n elements fo the array, but for each element, it is checking at least some part of the (n-1) other elements, creating a polynomial. We take the largest term in the polynomial and simplify it to say that "The number of instructions processed in the worst case will be on the order of n^2", or O(n^2).

Thankfully, in your case, I doubt you will be processing hundreds, thousands, or millions of questions, so we don't have to think any harder about better ways to do it. I don't have any off the top of my head right now, so I don't have one!

EDIT: I thought of one. You could set up a binary tree containing the questions you've selected so far, and finding whether or not a number has been picked would be O(log n) making the entire algorithm O(n log n). This is way overcomplicated for your efforts I just love algorithms!

Last edited by BigJ : 30-07-2012 at 20:27.
 


Thread Tools
Display Modes Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump


All times are GMT -5. The time now is 22:50.

The Chief Delphi Forums are sponsored by Innovation First International, Inc.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright © Chief Delphi