algorithm - Recursive tree with constant - T(n) = T(n/3) + T(2n/3) + cn -


I have a task and there is a slight problem with it, but I could not find the answer.

Explain that solution using the recurring tree: T (n) = t (n / 3) + t (2n / 3) + cn where is constant, omega (n lg n) < / P>

My solution: 1. T (n) = t (n / 3) + t (2n / 3) + cn

The shortest route will be left most because it is running at the lowest price, and the longest most accurate , Which means that Ed is not balanced.

The lowest path can be defined: n -> 1/3 n -> (1/3) ^ 2 n -> ...-> 1

  1. CN value on recurring tree:

The sum of each full level is equal to CN.

  1. Divisor from the lowest path is being divided by 3, the length of this path will be equal to logon. So if the full level of the recurring tree for the least route Logon is equal to n, then it means that the cost of algorithms for this path will be: T (n) = cn logon n = omega (cn lg n)

Is this solution correct? is? How to get rid of "C" in the form of a task to explain Omega (N \ LG N) and Omega (CNG LG N)? I thought the big omega marking would help and I could just ignore "C", but my teacher said that "continuously [I do not know what definition] is important according to the definition"

Yes, your solution is correct and yes, you can ignore continuous omega (c * n * log n) is the same as omega (n * log n) if c is a constant (according to f (n) = omega (g) If there is such a C0> 0 and N0 exist, then N> = N0 f (n)> = C0 * G (n) . If we have g (n) = c * g (n) , we can just choose C0 '= C0 * c ) Are there.


Comments

Post a Comment

Popular posts from this blog

python - Overriding the save method in Django ModelForm -

I'm having trouble overriding a ModelForm save method. I get this error I'm: Exception type: TypeErier Exception Value: Save () found an unexpected keyword argument 'committed' My intentions include a form 3 fields Submit several values ​​for, then create an object for each combination of those areas, and to save each object file models.py class collarsult type (models.Model): id = model. AutoField (db_column = 'icontact_result_code_type_id', primary_key = true) callResult = models.ForeignKey ( 'CallResult', db_column = 'icontact_result_code_id') campaign = models.ForeignKey ( 'campaign', db_column = 'icampaign_id') CALLTYPE = models.ForeignKey ( 'CALLTYPE', db_column = 'icall_type_id') agent = models.BooleanField (db_column = 'bagent', default = true) teamLeader = models.BooleanField (db_column = 'bTeamLeader', default = true) active = models.BooleanField (db_column = Django.form...
Read more

html - CSS autoheight, but fit content to height of div -

I have a div in which there are three children- div in the left and middle div: float: left while true: float: true because it is my layout Actually will spoil, I've used ClearFix Hack: .cf {zoom: 1; }. Cf: First,. Cf: {content: ""; Display: Table; }. Cf: After {clear: both; } It still works, but I want to be the right div an indicator. So it should fill 100% of the parent unit of height. How can I complete this? PS is the full code: & Lt; / Div & gt; & Lt; Div class = "mobile_content" & gt; & Lt; H5 & gt; {{Data.titel}} & lt; / H5> & Lt; Table & gt; & Lt; TR & gt; & Lt; Th & gt; Komponist: & lt; / Th & gt; & Lt; TD & gt; {{Data.komponist}} & lt; / TD & gt; & Lt; / TR & gt; & Lt; TR & gt; & Lt; Th & gt; Instrument: & lt; / Th & gt; & Lt; TD & gt; {{Data.instrumente}} & lt; / TD & gt; & Lt; / TR & gt;...
Read more

qt - How to prevent QAudioInput from automatically boosting the master volume to 100%? -

I have been trying to use Qt5 multimedia to record audio with QAudioInput, however, when I see If QAudioInput is started, it increases the master volume of my sound device to 100%. How can I prevent QAudioInput from changing the master volume? My current development platform is Linux with PalsAdio (with flat audio disabled). How can I use QAudioInput : QAudioDeviceInfo device_info = QAudioDeviceInfo :: defaultInputDevice (); QAudio format format; Format.setSampleRate (44100); Format.setChannelCount (1); Format.setSampleSize (16); Format.setCodec ("Audio / PCM"); Format.setSampleType (QAudioFormat :: SignedInt); Format.setByteOrder (QAudioFormat :: LittleEndian); Std :: cout & lt; & Lt; Device_info.deviceName (). ToUtf8 (). ConstData () & lt; & Lt; Std :: endl; QAudioInput * default_device = new QAudioInput (device_info, format); QIODevice * default_io_device = default_device-> Start (); a QAudioInput.setVolume () method is not you I ...
Read more