Блог пользователя adamantium

What is the actual complexity of 620C
Автор adamantium, история, 9 лет назад, По-английски

In 620C - Pearls in a Row I watch some source code of other people. Most of them used map. They iterate for n times and count the element of the array using map when they find that the value of current element in the map is 2 then they clear the whole map.. For that I am bit confused about that solution. It will be pleasure if anyone tell me what is the actual complexity of that solution :)

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

to delete all the elemants in map take O(N) where N is size of map

sum of all the sizes of map during program, about what you have said, is N

so such solution as you say take O(N + NlogN)

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

Best way to do it is using set just because we dont need to count elements : we only need to know if this element was before. Anyway, in java you can clear map(in my case set) with O(1) complexity like this:

set = new TreeSet<>();

BTW, if we change it to HashSet(unordered_set in c++), we can get O(n) complexity.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If I'm not mistaken, old set will be cleared away by GC, and it will still take O(n) time

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Old set will be cleared by GC of corse but please explain me why do you think that it take O(n) time?

      I don't know right answer, but I can share my thoughts: complexity is O(1) because we don't remove each element separately, we remove the whole object from the memory.

      Anyway, I made an experiment and get some data which confirms my thesis:

      k = 5
	Adding time: 0
	Clearing time: 0
k = 10000
	Adding time: 8
	Clearing time: 0
k = 1000000000
	Adding time: 7316
	Clearing time: 0
      → Ответить