[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Временска сложеност  XML
Forum Index » C/C++
Author Message
Tose Todorov



Joined: 23/02/2016 21:45:08
Messages: 15
Offline

За програмирање почнав посериозно да се интересирам пред 3-4 месеци и некои работи уште не ми се јасни па ако може некој да ми објасни нешто

Случајно ја отворив задачата Роденденски прослави и без да ја дочитам ми текна решение и почнав да пишувам. Сигурно има пооптимално решение, уште се немам обидено да ја решам на друг начин затоа што ме интересира зошто ова решение ми го надминува временскиот лимит за 2 тест примери.



Во долниот дел од програмата мислам дека нема никаков проблем бидејќи 2та for циклуси се извршуваат 12 пати и имаат еден if statement со по една наредба, а последниот може да се изврши од 1 до макс 12 пати и има 1 наредба. 3те циклуси заедно не би требало да имаат поголема сложеност од 100.

Претпоставувам дека проблемот ми е во најгорниот for циклус но не можам да сфатам точно до што е проблемот.



За овој циклус би требало да имам сложеност n*O(5) (ако се смета и if во наредбите?). На мене програмата ми го надминува лимитот зa еден тест пример каде што n=100 000 а за другиот нз колку е n, го немам симнато тој пример. За n=100 000 би требало да се извршат околу 500 000 операции а еден компјутер може да изврши многу повеќе во една секунда, па не сфаќам зошто програмата го надминува временскиот лимит. Дали пристапувањето до членови во повеќедимензионална низа како има голема сложеност или до што е проблемот ако може некој да ми објасни?

MOI



Joined: 07/07/2010 16:31:48
Messages: 447
Offline

Tose Todorov wrote:За програмирање почнав посериозно да се интересирам пред 3-4 месеци и некои работи уште не ми се јасни па ако може некој да ми објасни нешто

Случајно ја отворив задачата Роденденски прослави и без да ја дочитам ми текна решение и почнав да пишувам. Сигурно има пооптимално решение, уште се немам обидено да ја решам на друг начин затоа што ме интересира зошто ова решение ми го надминува временскиот лимит за 2 тест примери.

Хм, системот не вика дека имаш надминат временски лимит, туку дека се појавува грешка при извршувањето на твојата програма.

Доколку те интересира што е грешката, прочитај го првиот дел од ова предавање: http://mendo.mk/Lecture.do?id=21
Накратко, ако имаш низа array[12], тогаш таа има големина од 12 елементи, и можеш да запишуваш на позициите: array[0], array[1], ... array[11], но не и array[12]. Слично и со матрици.
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

Најозбилно , ако седнеш да решаваш задача па макар и 2 дена или цела недела ќе ја решиш но кога најтешко е да се справиш со надминат временски лимит
најчесто за надминат временски лимит колку што ми кажуваа мене да се користат STL библиотеките , наместо Pass by value , да користам Pass by reference ... уствари почесто да ги користиме покажувачите...
 
Forum Index » C/C++
Go to:   
Powered by JForum 2.1.8 © JForum Team